  Link failures in wide area networks are common and cause significant data
losses. Mesh-based protection schemes offer high capacity efficiency but they
are slow and require complex signaling. Additionally, real-time
reconfigurations of cross-connects threaten their transmission integrity. On
the other hand, there are other schemes that are proactive. Proactivity results
in higher restoration speed, lower signaling complexity, and higher
transmission integrity. This paper introduces a coding-based proactive
protection scheme, named Coded Path Protection (CPP). In CPP, a backup stream
of the primary data is encoded with other data streams, resulting in capacity
savings. In addition to a systematic approach of building valid coding
structures, this paper presents an optimal and simple capacity placement and
coding group formation algorithm. The algorithm converts the sharing structure
of any solution of a Shared Path Protection (SPP) technique into a coding
structure with minimum extra capacity. We conducted quantitative and
qualitative comparisons of our technique with the SPP. Simulation results
confirm that CPP provides faster link failure recovery than SPP while it incurs
marginal extra capacity beyond that of SPP. In this Part 1 of the paper, we
describe the theory and an algorithm for converting a given SPP solution into a
CPP solution.
