2-Approximation algorithm for for messages across a cyclic network
Start with an integer program for your problem.
For each $i$, there is a variable $x_i \in \{0,1\}$ which represents which way the $i$'th message is routed. You can express the number of messages going through an edge $e$ as some linear combination $y_e$ of the $x_i$'s. Your goal is to minimize $\max(y_e)$. Equivalently, you want to minimize $m$ under the constraints $m \geq y_e$.
Now consider the LP relaxation. Determine which way to route the $i$'th message by rounding $x_i$.