From van@lbl-csam.arpa Mon Nov 2 16:44:19 1987 Posted-Date: Mon, 02 Nov 87 16:40:53 PST Received-Date: Mon, 2 Nov 87 16:44:19 PST Received: from LBL-CSAM.ARPA by venera.isi.edu (5.54/5.51) id AA06264; Mon, 2 Nov 87 16:44:19 PST Received: by lbl-csam.arpa (5.58/1.18) id AA23401; Mon, 2 Nov 87 16:40:55 PST Message-Id: <8711030040.AA23401@lbl-csam.arpa> To: ddc@xx.lcs.mit.edu Cc: end2end-interest@venera.isi.edu Subject: TOS routing Date: Mon, 02 Nov 87 16:40:53 PST From: Van Jacobson Dave - At the end2end meeting, we had a brief discussion about TOS routing. My recollection is that you were worried that having a continuous range of types of service (e.g., packet can specify delay < X and throughput > Y for arbitrary X & Y) would force routes to be computed from scratch every time a new connection started up (of course, my recollection and your statements probably bear no resemblence to one another). I said that for fixed link capacities and delays, there were only a finite number of places where routing could effect delay or throughput thus one could envision a routing algorithm that computed the available ranges of delay and throughput as it computed paths. I think the conversation concluded on the note that this might be possible but the algorithm would be expensive and the routing tables might get huge. I remembered a recent paper about such a partitioning algorithm and looked it up when I got home. "A Fast Parametric Maximum Flow Algorithm" by G. Gallo, M.D. Grigoriadis and R.E. Tarjan, July, 1987 (Rutgers Department of Computer Science technical report LCSR-TR-95) seems like just the thing. It's a simple extension to Goldberg and Tarjan's "preflow" algorithm (which is itself a nifty idea that might work well for network routing) that will give all cuts or ranges in a network with parametric capacities as fast or faster than Ford-Fulkerson will give you min-hop. The algorithm looks parallizable, i.e., close enough to Ford-Fulkerson that the distributed Bellman-Ford routing ideas we use now should apply. [The paper contains several algorithms and applications. I'm looking at the "finding all breakpoints" algorithm in section 3.3. There's also a note in sec. 3.5 on representing the complete set of cuts in a structure that's linear in the number of vertices of the net. I.e., the routing tables don't have to get much bigger.] - Van