The main result of this section is summarized in the following theorem.
Proof: There are three phases to the algorithm. First, packets originating at bad nodes are deterministically routed to the good nodes with which they are associated. By Lemma 5.4 this phase requires steps. Next, packets are routed between the good nodes on the logical network. Since at most bad nodes are associated with each good necklace, with high probability the congestion of the paths on the logical network is , by Lemma 5.3. Thus, this phase requires steps, with high probability. The packets are routed in steps using the scheduling algorithm from Section 2. Finally, packets destined for bad nodes are deterministically routed from the good nodes to bad. By an analysis similar to that of Lemma 5.4, this phase also requires steps.