Communication latency II

Also today's homework asks you to solve two problems, the first one very easy.
1. Prove that the upper bound on link congestion during the direct-exchange AAS in WH 1-port full-duplex M(z1,z2) in Subsection 14.4.2 is
max(z1,z2)/2.

Note that the mesh uses XY-routing.
2. Derive expression for the communication latency of an optimal combining all-to-all broadcast on a store-and-forward 1-port full-duplex T(z1,z2), where z1,z2 are odd numbers.
• In one round, one node can exchange one message with only one neighbor.
• Initially, every node holds one packet of size \mu.
• The communication latency of exchanging a packet of size M between two neighbors is
t(M)=ts+M tm.

• Make sure that the algorithm is NOHO and NODUP. This gives you the exact message sizes in every step and therefore exact latency.
• Solve the problem first for 1-D torus (algorithm 2 in Subsection 13.1.3) and then generalize the solution to 2-D torus as suggested by Figure 13.6.
• If z1\not=z2, does the latency depend on whether the nodes perform first the horizontal AAB and then the vertical one or vice versa?
• How these results change if z1 and z2 are any integers, not only odd?
• If possible, try to generalize these results to arbitrary T(z1,...,zn).