Previous | Next --- Slide 20 of 51
Back to Lecture Thumbnails
pavelkang

Min latency given by topology is the theoretical lower bound of this network, which is the shortest path between two vertices in the graph. Min latency given by routing algorithm is larger since not all communications happen on the shortest path. In case of contention, the routing algorithm might create detours in order to get higher overall throughput. I am curious why flow control and routing are two different things. It seems to me that a routing algorithm should deal with both.

althalus

@pavelkang, I think routing is the algorithm to get the fastest way for a message to go from point A to B while flow control is usually a way to manage the throughput (rate) of transmission of data to protect the data's integrity.

MaxFlowMinCut

I think the routing algorithm could also be the overhead associated with looking up a route in a routing table to figure out where to forward a packet, and maintaining that routing table. The overhead in doing so isn't much, but it's also non-negligible.

Edit: Note that not all algorithms might use a "routing table" per se, but I think that's the intuition that the routing latency is trying to capture.

jhibshma

I believe that the shape of the curve, while never having a negative derivative, could definitely vary. For instance, consider a directed network consisting of just two "paths": several lines running from A to B and others from B to A. In this case, latency does not increase with traffic. That is, it doesn't increase with traffic until you hit more traffic than the network's top bandwidth, at which point the latency begins to increase without bound. <-- Is that correct?

PandaX

@pavelkang, I believe the flow control means a mechanism for temporarily stopping the transmission of data on networks to alleviate the heavy traffic.

In real condition, routing and flow control are both applied.

xingdaz

If it helps, draw the analogy to the internet. Throughput given by the topology is what is theoretically possible given how your nodes are physically connected. For example, in data centers, fat tree topology is used. Throughput given by routing is what is possible with a particular routing scheme you choose given the topology. It is like routing a packet with IP protocol. Throughput by flow control is what is given to us by the transport protocol that reassembles or retransmits messages. Think TCP.