[ih] Overlay networks

[Lawrence Stewart]

After the discussion about the Arpanet routing being shortest path I am wondering if anyone experimented with overlay networks.

If the hosts know the the topology and the network routing algorithm, they can build a network with a different routing algorithm on top of the existing network by essentially doing store and forward at the hosts while using the base network only as links.

The first time I heard of this was Sandia Labs work on GUPS (or HPCC Random Access) in 2004, which achieved much better than expected results on Red Storm by aggregating small application messages for transport over the base network.  A small message might traverse the base network several times, but the advantage of large messages was so great that it overcame the inefficiency.

The idea also turns up in collective algorithms in MPI, SHMEM, and others.

-L