What does a sample of blocking network look like? It's hard to image a network where somebody in the network cannot connect to each other. (sorry I found the example in the next slide)
uncreative
I'd just like to add to the definition of the bisection bandwidth, since there was some confusion which was resolved in the review session.
The bisection bandwidth is the bandwidth across the minimum cut which divides the network into two equal partitions.
So, it is the amount of bandwidth you are guaranteed to have between two halves of the network no matter how you divide it.
And from wikipedia
"If the network is segmented into two equal parts, this is the bandwidth between the two parts.[1] Typically, this refers to the worst-case segmentation, but being of equal parts is critical to the definition, as it refers to an actual bisection of the network."
jezimmer
@uncreative: How would this apply to a network like the multistage logarithmic network, i.e., a network that's indirect? What are we partitioning, the nodes themselves or the nodes and the switches? (Or does it not matter?)
I guess I'm just confused as to what the bisection bandwidth of the multistage logarithmic topology is.
chenliu
@jezimmer I would say only the nodes matter. Some references: http://www.cs.utah.edu/~rajeev/cs6810/pres/07-6810-23.pdf slide 9, and in http://eprints.networks.imdea.org/274/1/J.Arjona-MsC Thesis-September2011.pdf section II A, where bisection bandwidth is more formally defined by each half having half of the number of nodes.
chenliu
@uncreative With that definition, bisection bandwidth of the multistage topology with n nodes should just be n/2.
BryceToTheCore
@jezimmer I believe that in the main example multistage logarithmic example with 8 nodes to a side, the bisection bandwidth is probably 8, because no matter how you slice it I count 8 links that need to be severed to split the network in half.
chenliu
@BryceToTheCore You can get 10 too, by drawing a line starting from the link next to node 0 (on the next slide) and ending at the link next to node 7.
BryceToTheCore
@chenliu I believe that those same nodes that could be separated by the 10 link cut, could be separated with an 8 link cut instead. I think my hypothesis is that the nodes cannot be separated by a 7 link cut.
The cut is a lower bound, not an upper bound.
chenliu
@BryceToTheCore I agree with you on that. That's also why I said it's n/2 (just a hypothesis too). I mistook what you said in your second last post.
I probably should say the min-cut is n/2, but the bandwidth is O(n/2). (or simply O(n)?)
toothless
@BryceToTheCore Assuming that you're only interested in cuts that split the left side of the graph from the right side, then here's an easy proof that the bandwidth is exactly 8: there is a flow of size 8 from the left side to the right, since you can just send 1 flow right along every edge. So the max flow is at least 8, which means the min-cut is at least 8. Since you found a min-cut of size 8, the desired bandwidth is exactly 8. In general, the bandwidth is always exactly n/2.
What does a sample of blocking network look like? It's hard to image a network where somebody in the network cannot connect to each other. (sorry I found the example in the next slide)
I'd just like to add to the definition of the bisection bandwidth, since there was some confusion which was resolved in the review session.
The bisection bandwidth is the bandwidth across the minimum cut which divides the network into two equal partitions.
So, it is the amount of bandwidth you are guaranteed to have between two halves of the network no matter how you divide it.
And from wikipedia
"If the network is segmented into two equal parts, this is the bandwidth between the two parts.[1] Typically, this refers to the worst-case segmentation, but being of equal parts is critical to the definition, as it refers to an actual bisection of the network."
@uncreative: How would this apply to a network like the multistage logarithmic network, i.e., a network that's indirect? What are we partitioning, the nodes themselves or the nodes and the switches? (Or does it not matter?)
I guess I'm just confused as to what the bisection bandwidth of the multistage logarithmic topology is.
@jezimmer I would say only the nodes matter. Some references: http://www.cs.utah.edu/~rajeev/cs6810/pres/07-6810-23.pdf slide 9, and in http://eprints.networks.imdea.org/274/1/J.Arjona-MsC Thesis-September2011.pdf section II A, where bisection bandwidth is more formally defined by each half having half of the number of nodes.
@uncreative With that definition, bisection bandwidth of the multistage topology with n nodes should just be n/2.
@jezimmer I believe that in the main example multistage logarithmic example with 8 nodes to a side, the bisection bandwidth is probably 8, because no matter how you slice it I count 8 links that need to be severed to split the network in half.
@BryceToTheCore You can get 10 too, by drawing a line starting from the link next to node 0 (on the next slide) and ending at the link next to node 7.
@chenliu I believe that those same nodes that could be separated by the 10 link cut, could be separated with an 8 link cut instead. I think my hypothesis is that the nodes cannot be separated by a 7 link cut.
The cut is a lower bound, not an upper bound.
@BryceToTheCore I agree with you on that. That's also why I said it's n/2 (just a hypothesis too). I mistook what you said in your second last post.
I probably should say the min-cut is n/2, but the bandwidth is O(n/2). (or simply O(n)?)
@BryceToTheCore Assuming that you're only interested in cuts that split the left side of the graph from the right side, then here's an easy proof that the bandwidth is exactly 8: there is a flow of size 8 from the left side to the right, since you can just send 1 flow right along every edge. So the max flow is at least 8, which means the min-cut is at least 8. Since you found a min-cut of size 8, the desired bandwidth is exactly 8. In general, the bandwidth is always exactly n/2.