[Talks] Brown CS Thesis Defense: Costas Busch talk in Lubrano Conference Room on 5/3/2000 at 11:00 am

[talks-admin@list.cs.brown.edu]

			  CS Thesis Defense
		  The Department of Computer Science
			   BROWN UNIVERSITY

			       presents

			     Costas Busch		     


		  Wednesday, May 3, 2000 at 11:00 AM

	       Lubrano Conference Room (CIT 4th floor)
	
	          
		    ``Greedy Hot-Potato Routing''

			       
			       Abstract


We present new hot-potato communication algorithms for the mesh
network.  In hot-potato routing, the nodes of the network have no
buffers to store messages in transit, thus causing the messages to
move from node to node each time, namely, the messages are treated
like ``hot-potatoes''. Hot-potato routing has immediate applications in
optical networks, where the messages are made from light which is
difficult to be stored. An interesting class of hot-potato routing
algorithms are the so called ``greedy'' algorithms in which the messages
simply try to get closer to their destinations.  It has been observed
that the greedy algorithms perform extremely well in practice;
however, there has been no adequate formal analysis that could explain
this good behavior. The hot-potato algorithms we present in this talk
are greedy with improved theoretical bounds, which give the first
formal explanation of the good behavior of greedy algorithms. A key
technique in our algorithms is the use of randomization to adjust
priorities of messages.


  
		     Host: Professor Maurice Herlihy