Appendix of Paper "Traffic Engineering with Forward Fault Correction" - Liu, Hongqiang; Kandula, Srikanth; Mahajan, Ratul; Zhang, Ming (Microsoft Research, 2014)
This is an appendix for paper "Traffic Engineering with Forward Fault Correction" published in SIGCOMM 2014. In our recently published paper [1], we propose a method which leverages bubble sorting network to transfer “ Bounded M-sum constraint” into an efficient format. In Section 4.4.2, we show in Figure 8(c) that we use linear formulations to en-code the constraints in lines 10 and 11 of Algorithm 2. Nevertheless, this encoding is not precise. The linear constraints in Figure 8(c) is only approximating the original constraints with absolute value formats in Algorithm 2. In this technical report, we will explain why our bubble sorting network method and FFC implementation are valid despite of the preceding imprecision of the linear formulation. We will proof that the linear formulation shown in Figure 8(c) is sufficient to guarantee that the final TE this formulation computes satisfies all FFC requirement.