Note that a Ring network has lower contention than a Bus since the interconnect is a shared resource by each node on the Bus but in a Ring we can have multiple simultaneous transmissions of data (Ex. from 0 to 3, 0 to 1, 1 to 2, 2 to 3 in the figure above).
hofstee
In a worst case scenario would the ring behave equivalently to a bus?
temmie
@hofstee I think they're a bit different because on a bus, any message always gets broadcast from the sending node to all other nodes, whereas rings (as far as we've discussed them) are used to send messages from the source node to a single destination node. Every time a message goes out on the bus, it uses the whole bus, because it needs to reach every node, whereas in a ring we only need the segments connecting the source to the destination, allowing for the "multiple simultaneous transmissions of data" that @Calloc describes.
In the ring's worst case for a given message, the destination is directly across the ring from the source, so we're still not using the entire network and could potentially send other messages simultaneously. It should also have lower latency than the equivalent on a simple bus interconnect, simply because the distance between the furthest nodes is halved, though it would depend on the particular implementation of each.
Khryl
Could anyone illustrate why bisection bandwidth remains constant as nodes are added? And how does this cause scalability issue?
temmie
@Khryl "Bisecting" is just cutting in half: dividing the ring so that half of the nodes are on either side. Then the bandwidth is the number of segments you cut for the bisection, the number of wires that were connecting those two halves. When you cut a ring in half, no matter how many total nodes are on it, you will cut exactly two segments. You can imagine splitting a circle of string into two equal-length strings--regardless of how long the circle is to begin with, you will need to cut it exactly twice.
@jrgallag has a good explanation of bisection bandwidth (and why we want more of it) on slide 18, here: http://15418.courses.cs.cmu.edu/spring2016/lecture/interconnects/slide_018
Essentially, having exactly two potential routes between either half of the network quickly becomes a bottleneck for network traffic. For 4 nodes, two routes is pretty good, but for 64 it's terrible, so we'd like bisection bandwidth to scale with the number of nodes.
hofstee
@temmie but what if everyone wanted to only send messages to node 1?
temmie
@hofstee That's kind of the reverse of node 1 broadcasting a message on a bus in the sense that one node is trying to communicate with all other nodes, but the situations are still pretty different. In the ring's worst case, we'd be considering P-1 messages trying to get to a single node, and they'd be competing with each other for access to the wire and potentially choosing different routes to get there. In the bus, it would just be one node broadcasting a message as normal. I guess it depends on what you mean by "behave equivalently"? I don't believe latency or wire usage would be similar between the two.
PandaX
I think bisection bandwidth measures the bottleneck exists in the network, right?
krillfish
It seems like it (about bisection bandwidth and bottleneck). If the bisection bandwidth is how many ways you can cut the network, then it's like how many paths you can take to other sources/destination. Therefore, with a smaller bisection bandwidth, there are only so few paths that you can take, and other sources will be using the same paths, resulting in a bottleneck.
IntergalacticPeanutMaker
Is the latency O(n) for both a uni and bi directional ring? Also I suppose a uni directional ring would have almost no contention.
Updog
Both uni and bi directional rings will have O(n) latency. I think that a unidirectional ring will have more contention than a bidirectional ring, but still less than a bus. For example, in the ring above consider transmissions 0 to 1 and 3 to 2 happening simultaneously. For a bidirectional ring there would be no contention, but there would be contention in the unidirectional case.
rmanne
The internet would probably be some cross between a ring and a loose mesh, right? If every city was to be connected to every adjacent city even, that might cost too much. And within one, houses probably are in a ring, rather than a mesh. Could the internet be seen as such a system?
Lotusword
The average distance is N/2 with unidirectional links, and N/3 with bidirectional links. The bisection width is one.
Note that a Ring network has lower contention than a Bus since the interconnect is a shared resource by each node on the Bus but in a Ring we can have multiple simultaneous transmissions of data (Ex. from 0 to 3, 0 to 1, 1 to 2, 2 to 3 in the figure above).
In a worst case scenario would the ring behave equivalently to a bus?
@hofstee I think they're a bit different because on a bus, any message always gets broadcast from the sending node to all other nodes, whereas rings (as far as we've discussed them) are used to send messages from the source node to a single destination node. Every time a message goes out on the bus, it uses the whole bus, because it needs to reach every node, whereas in a ring we only need the segments connecting the source to the destination, allowing for the "multiple simultaneous transmissions of data" that @Calloc describes.
In the ring's worst case for a given message, the destination is directly across the ring from the source, so we're still not using the entire network and could potentially send other messages simultaneously. It should also have lower latency than the equivalent on a simple bus interconnect, simply because the distance between the furthest nodes is halved, though it would depend on the particular implementation of each.
Could anyone illustrate why bisection bandwidth remains constant as nodes are added? And how does this cause scalability issue?
@Khryl "Bisecting" is just cutting in half: dividing the ring so that half of the nodes are on either side. Then the bandwidth is the number of segments you cut for the bisection, the number of wires that were connecting those two halves. When you cut a ring in half, no matter how many total nodes are on it, you will cut exactly two segments. You can imagine splitting a circle of string into two equal-length strings--regardless of how long the circle is to begin with, you will need to cut it exactly twice.
@jrgallag has a good explanation of bisection bandwidth (and why we want more of it) on slide 18, here: http://15418.courses.cs.cmu.edu/spring2016/lecture/interconnects/slide_018
Essentially, having exactly two potential routes between either half of the network quickly becomes a bottleneck for network traffic. For 4 nodes, two routes is pretty good, but for 64 it's terrible, so we'd like bisection bandwidth to scale with the number of nodes.
@temmie but what if everyone wanted to only send messages to node 1?
@hofstee That's kind of the reverse of node 1 broadcasting a message on a bus in the sense that one node is trying to communicate with all other nodes, but the situations are still pretty different. In the ring's worst case, we'd be considering P-1 messages trying to get to a single node, and they'd be competing with each other for access to the wire and potentially choosing different routes to get there. In the bus, it would just be one node broadcasting a message as normal. I guess it depends on what you mean by "behave equivalently"? I don't believe latency or wire usage would be similar between the two.
I think bisection bandwidth measures the bottleneck exists in the network, right?
It seems like it (about bisection bandwidth and bottleneck). If the bisection bandwidth is how many ways you can cut the network, then it's like how many paths you can take to other sources/destination. Therefore, with a smaller bisection bandwidth, there are only so few paths that you can take, and other sources will be using the same paths, resulting in a bottleneck.
Is the latency O(n) for both a uni and bi directional ring? Also I suppose a uni directional ring would have almost no contention.
Both uni and bi directional rings will have O(n) latency. I think that a unidirectional ring will have more contention than a bidirectional ring, but still less than a bus. For example, in the ring above consider transmissions 0 to 1 and 3 to 2 happening simultaneously. For a bidirectional ring there would be no contention, but there would be contention in the unidirectional case.
The internet would probably be some cross between a ring and a loose mesh, right? If every city was to be connected to every adjacent city even, that might cost too much. And within one, houses probably are in a ring, rather than a mesh. Could the internet be seen as such a system?
The average distance is N/2 with unidirectional links, and N/3 with bidirectional links. The bisection width is one.