tds@cbnewsh.ATT.COM (antonio.desimone) (11/15/89)
Can someone point me to a source of information on cisco's Interior Gateway Routing Protocol? I've come across some of their glossies that make mention of flow optimization, delay and traffic measurements, etc. I wonder if they do something much more sophisticated than, for example, Open SPF as far as load balancing (if I understand Open SPF, the protocol allows round-robin routing over equal shortest paths). Beyond cisco in particular, are there any IP router vendors who attempt to make routing decisions based on real-time traffic measurements? I'm not talking about neat experimental algorithms, or unused options in some protocol, but commercial (or at least widely used) implementations. My impression, based on an admittedly cursory scan of the literature, is that a lot of interesting work has been done but nobody has solved the stability and measurement/timescale problems to the extent that someone would risk such an algorithm in an operational network or a commercial product. -- Tony DeSimone AT&T Bell Laboratories Holmdel, NJ 07733 att!tds386e!tds
kwe@bu-cs.BU.EDU (kwe@bu-it.bu.edu (Kent W. England)) (11/16/89)
In article <5764@cbnewsh.ATT.COM> tds@cbnewsh.ATT.COM (antonio.desimone) writes: >Can someone point me to a source of information on cisco's >Interior Gateway Routing Protocol? Chuck Hedrick from Rutgers recently announced formation of an Open Distance Vector Routing Working Group within the IETF and has drafted a paper on cisco's IGRP (with cisco's permission) as a candidate for that protocol. Anon ftp is available from one of several servers at rutgers.edu. Try athos.rutgers.edu in /pub/igrp.[doc|ps]. It might be or will be in the Working Group directories on SRI-NIC at some point. So, for the first time, there is a rather complete description of cisco's patented (or patent pending) algorithm. >... I wonder if they do something much more >sophisticated than, for example, Open SPF as far as load balancing >(if I understand Open SPF, the protocol allows round-robin routing >over equal shortest paths). Well, the main diff is link-state versus distance-vector. OSPF is link-state and ciscoIGRP is distance vector. Depending on which side you light your torch, you might prefer one over the other based on link-state or distance-vector. > >Beyond cisco in particular, are there any IP router vendors who >attempt to make routing decisions based on real-time traffic >measurements? I'm not talking about neat experimental algorithms, >or unused options in some protocol, but commercial (or at least >widely used) implementations. My impression, based on an >admittedly cursory scan of the literature, is that a lot of >interesting work has been done but nobody has solved the stability >and measurement/timescale problems to the extent that someone >would risk such an algorithm in an operational network or a >commercial product. Oh, I don't know. The first NSFnet backbone risked a delay/congestion based algorithm on an operational (but noncommercial) network.
eason@ncrcce.StPaul.NCR.COM (Dale Eason) (11/17/89)
Where can I find more information on the differences and relationships between Cisco's IGP, Proteon's OSPF, and RIP. We are trying to build a network and need to know how to get the routing done.
medin@NSIPO.NASA.GOV ("Milo S. Medin", NASA ARC NSI Project Office) (11/17/89)
Just a point of clarification here about OSPF. The protocol will find multiple equal-cost paths. Whether or not a router can use this information to load-balance in a round-robin way depends on how the IP forwarding module in a particular implementation is implemented. In general trying to do dynamic load balancing in a multi-vendor environment is a pretty dicey issue. BBN went through great pains to tame the dynamic load balancing in their PSN networks. Thanks, Milo
forster@CISCO.COM (Jim Forster) (11/17/89)
Dale, If you would like to read about the algorithms and protocols, IGRP is described in the document igrp.ps or igrp.doc, on ftp.cisco.com (131.108.1.27. The 'dir' command is disabled on that machine, but you may use 'get' on those filenames). OSPF is described in RFC1131, and RIP in 1058. The algorithms & protocols described by these documents are only part of the answer to your question. Implementations can have important features, which allow one to control who is listened to and believed, for instance, which are not neccessarily part of the specification. Jim Forster cisco Systems
swb@DAINICHI.TN.CORNELL.EDU (Scott Brim) (11/21/89)
>Oh, I don't know. The first NSFnet backbone risked a delay/congestion >based algorithm on an operational (but noncommercial) network. The implementation of the HELLO protocol used in the first NSFNET backbone (on fuzzballs, by Dave Mills) was supposed to be independent of load on the net, in that the routing messages were generated just barely outside of the interface cards themselves. There turned out to be some wobble, and Dave put a lot of work into controlling and damping the incredible thrashing that occasionally came about due to that wobble (also gated had a sliding window and filter put in to damp it even further). I don't know anyone who's working on dealing with these problems for large nets anymore. The main problem is that you're in a situation where the system can (and probably will) change direction faster than you can detect a wobble, send out an adjustment to it, and have your adjustment stabilize. You just keep thrashing. Scott
dlj@proteon.com (Daniel L. Jones) (11/21/89)
Dale, Give me a call or send me email and I'll send you the OSPF spec. Ask cisco customer service for the IGRP spec. You can read about RIP in Doug Comer's Book " Internetworking with TCP/IP". Dan Jones Proteon Customer Service (508) 898-3100 dlj@proteon.com
tsuchiya@GATEWAY.MITRE.ORG (11/21/89)
The only work still going on for traffic-based routing in connectionless networks, that I know of, is at BBN. They have published a nice paper on recent work in this area in SIGCOMM 89. The paper is nice both for the algorithms they present and for the general description of the nature of the problem. The paper says to me that with a lot of tuning, delay-based routing can increase throughput in certain operating regions. But if it is poorly tuned, watch out. Of course, work of this sort associated with connection-oriented networks has been going on forever, but I can't say I'm too familier with the literature. In general, I think if yet another group is going to go off and work on another igp, it should do something different than the one we have, not just do the same thing a little better (and of course the verdict on whether DV can be better than LS is by no means in). Otherwise the headache of implementing to two standards is not worth the effort. For instance, doing delay-based routing, or multi-path (as a basic approach to routing, not just for equal paths), or multi-cast, or for that matter Landmark Routing. But these things require research, and so standardization would (and should) be delayed for some time. _________________________________________________________________ Paul F. Tsuchiya The MITRE Corp. tsuchiya@gateway.mitre.org 7525 Colshire Dr. 703-883-7352 McLean, VA 22102 USA _________________________________________________________________
tds@cbnewsh.ATT.COM (antonio.desimone) (11/22/89)
Some time back I posted this query (actually a longer version) looking for information on cisco's routing protocol. > Can someone point me to a source of information on cisco's > Interior Gateway Routing Protocol? I've come across some of their > glossies that make mention of flow optimization, delay and traffic > measurements, etc. I wonder if they do something much more > sophisticated than, for example, Open SPF as far as load balancing > Beyond cisco in particular, are there any IP router vendors who > attempt to make routing decisions based on real-time traffic > measurements? Thanks to all those who replied: I quote from some replies below. Kent> kwe%buitb.BU.EDU@bu-it.bu.edu (Kent England) John> John Bashinski <jbash@cisco.com> smb> ulysses!smb Milo> "Milo S. Medin" <ucbvax!nsipo.nasa.gov!medin> art> art@sage.acc.com First the quick summary: get the document describing IGRP written by Chuck Hedrick from Rutgers. Hedrick was good enough to send me a copy but I won't bother posting since it's available by anonymous ftp from: Kent> athos.rutgers.edu in /pub/igrp.[doc|ps]. It might Kent> be or will be in the Working Group directories on SRI-NIC at some Kent> point. John> You can pick up a copy of a paper on IGRP by anonymous FTP from John> ftp.cisco.com. It's called "igrp.doc". Directory listings are disabled John> for security reasons; just go ahead and pick up the paper. Basics: Kent> Well, the main diff is link-state versus distance-vector. OSPF is Kent> link-state and ciscoIGRP is distance vector. Depending on which side Kent> you light your torch, you might prefer one over the other based on Kent> link-state or distance-vector. Art> Until recently, IGRP was not being disclosed by cisco. At the last IETF, Art> Chuch Hedrick at Rutgers released a document (with cisco's OK), based Art> on the cisco patent application, which summarizes the major technology Art> in IGRP. From looking at that, I would say that OSPF and IGRP offer about Art> the same level of functionality. Of course, since IGRP is a Distance Vector Art> algorithm and OSPF is a Link State algorithm, this is somewhat apples to Art> oranges. cisco has apparently stated that they may be willing to liscense Art> IGRP much like Ethernet was (modest one time charge). Chuch Hedrick is Art> heading an IETF working group looking into defining a public domain Distance Art> Vector protocol that would be equal to or better than IGRP. On the issue of load balancing: John> IGRP provides for just slightly more than plain round-robin routing; you John> can specify a "variance", which allows load-sharing between links with John> different capacities. Unfortunately, large variances tend to destabilize John> the network. Milo> Just a point of clarification here about OSPF. The protocol will find Milo> multiple equal-cost paths. Whether or not a router can use this Milo> information to load-balance in a round-robin way depends on how Milo> the IP forwarding module in a particular implementation is implemented. Milo> In general trying to do dynamic load balancing in a multi-vendor Milo> environment is a pretty dicey issue. BBN went through great pains Milo> to tame the dynamic load balancing in their PSN networks. And on the use of measures of real-time congestion for routing: (I don't know if I was completely clear in my original posting. I was asking about controls that respond on the timescales on which queues build up. That's what is required to reroute rather than drop packets as queues build up, i.e. if you want "congestion avoidance".) smb> As for delay measurements: what about the ARPANET itself, where the IMPs smb> do real-time load measurements? That was certainly an operational net, smb> and MILNET still uses that technology. Art> The stability problems seem to outweigh any real benefits at the current Art> time. Until congestion avoidance mechanisms for connectionless networks Art> are developed (and deployed) to deal congestion in the first place, I Art> don't think it makes sense to try to respond to congestion at the routing Art> level. Once congestion avoidance mechanisms are there, and the routers Art> can determine the rate at which sources respond to congestion (not an easy Art> measurement problem) then that gives a limit to how fast routing should Art> be allowed to change. Art's statement seems to hold for the BBN/Milnet algorithm as well. There's an article in the recent SIGCOMM proceedings by Khanna and Zinky of BBN that explains the metric used. Yes delay measurements are used, but routes are updated on a timescale in the tens of seconds, at best. That approaches the connection (or at least the busy) time for file transfers. I think it's safe to say that no one uses rerouting as a congestion avoidance technique (although I'd still be interested to hear otherwise!) -- Tony DeSimone AT&T Bell Laboratories Holmdel, NJ 07733 att!tds386e!tds
Mills@UDEL.EDU (11/23/89)
Scott nicely and compactly summarized the problems with delay wobble in the NSFNET Phase-I network, now gone to heaven and reincarnated as a network of precision clocks. However, the real problem with the net as victim of congestion abuse was the link-level protocol (DDCMP) which was implemented in the interface firmware and could not be turned off. Thus, buffer starvation at one site would cause persistent retransmission and eventual stagflation at upstream sites. The many lessons learned, retroactively obvious and otherwise, are summarized in my paper "The Fuzzbll" appearing in SIGCOM 88 proceedings. Dave