Given an undirected graph G - (V; E0) with |V| = n, and a feasible weighted edge set E such that \mathis k-edge connected, the optimal k-edge connectivity augmentation problem is to find a subset \mathsuch that \mathis k- edge connected and the weighted sum of the edges in S is minimum, where k is a fixed integer. Since this problem is NP-complete for \math, in this paper we will focus on its approximation solution in the parallel environment. If G is (k - 1)-edge connected, the solution delivered by our NC approximation algorithm is within either twice the optimum if k is even, or 2t times the optimum otherwise, where \math. If G is \math- edge connected and \math, the solution delivered by our approximation algorithm is 2\mathtimes the optimum, where \mathis defined as follows: (i) if k and \mathare both odd or both even, then \math= \math; (ii) if k is even and \mathis odd, then \math= \math; (iii) otherwise, \math= \math.