{'fraction_non_alphanumeric': 0.04396831844029245, 'fraction_numerical': 0.015586921202274574, 'mean_word_length': 4.238563829787234, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Worst-case interference in DSL systems employing Dynamic Spectrum Management

Dynamic Spectrum Management (DSM) has been proposed to achieve next-generation rates on digital subscriber lines (DSL). Because the copper twisted-pair plant is an interference-constrained environment, the multiuser performance and spectral compatibility of DSM schemes are of primary concern. While the analysis of multiuser interference has been standardized for current static spectrum management (SSM) techniques, at present no corresponding standard DSM analysis has been established. This paper examines a multiuser spectrum-allocation problem and formulates a lower bound to the achievable rate of a DSL modem that is tight in the presence of the worst-case interference. A game-theoretic analysis shows that the rate-maximizing strategy under the worst-case interference (WCI) in the DSM setting corresponds to a Nash equilibrium in pure strategies of a certain strictly competitive game. A Nash equilibrium is shown to exist under very mild conditions, and the rate-adaptive waterfilling algorithm is demonstrated to give the optimal strategy in response to the WCI under a frequency-division (FDM) condition. Numerical results are presented for two important scenarios: an upstream VDSL deployment exhibiting the near-far effect, and an ADSL RT deployment with long CO lines. The WCI rate bound shows that the performance improvement of DSM over SSM techniques can be preserved by appropriate distributed power control, even in worst-case interference environments.


INTRODUCTION
In recent years, increased demands on data rates and competition from other services have lead to the development of new high-speed transmission standards for digital subscriber line (DSL) modems. Dynamic Spectrum Management (DSM) is emerging as a key component in next-generation DSL standards. As multiuser interference is the primary limiting factor to DSL performance, the potential for rate improvement by exploiting its structure is substantial.
DSM contrasts with current DSL practice known as static spectrum management (SSM). In SSM, masks are imposed on transmit power spectrum densities (PSDs) to bound the amount of crosstalk induced in other lines sharing the same binder group [1]. As SSM masks are fixed for all loop configurations, they can often be far from optimal or even prudent spectrum usage in typical deployments.
Spectral compatibility between different operators using DSM is a primary concern because new pathologies may arise with adaptive operation. However, in DSM a worst-case interference analysis based on maximum allowable PSDs is overly pessimistic, so existing spectral compatibility techniques cannot be fruitfully employed. A new paradigm is needed to assess the impact of DSM on multiuser performance of the overall system.

Prior Results
DSM algorithms have been proposed for the cases of distributed and centralized control scenarios. This paper considers what has been termed "Level 0-2 DSM" [2], wherein cooperation may be allowed to manage spectrum, but not for multiuser encoding and decoding. A centralized DSM center controlling multiple lines offers both higher potential performance and improved management capabilities [3]. Distributed DSM schemes based on the iterative waterfilling (IW) algorithm [4] have been presented. Numerous algorithms for centralized DSM have been proposed. [5] presents a technique to maximize users' weighted sum-rate. Optimal [6] and suboptimal [7] algorithms to minimize transmit power have been studied. An extensive suite of literature on upstream power-backoff techniques to mitigate the 'near-far' problem has been developed for static spectrum-management systems e.g. [8] [9].
In current DSL standards, upstream and downstream transmission use either distinct frequency bands or shared bands. In the latter case, "echo" is created between upstream and downstream transmission [4]. As analog hybrid circuits do not provide sufficient isolation, echo mitigation is essential in practical systems [10]. Numerous echo cancellation structures have been proposed for DSL transceivers e.g. [11] [12].

Outline
This paper formulates the achievable rate of a single "victim" modem in the presence of the worst-case interference from other interfering lines in the same binder group. The performance under the WCI is a guaranteed-achievable rate that can be used, for example, in studying multiuser performance of DSM strategies and establishing spectral compatibility of DSM systems. Section II defines the channel and system model. The WCI problem is formalized and studied in Section III from a game-theoretic viewpoint. Certain properties of the Nash equilibrium of this game are explored. Section IV considers numerical examples in VDSL and ADSL systems. Concluding remarks are made in Section V.

Channel Model
A copper twisted-pair DSL binder is modelled as a frequencyselective multiuser Gaussian interference channel [4] [13]. The binder contains a total of L + 1 twisted pairs, with one DSL line per twisted pair.

Modem Architecture
The standardized [14] discrete multitone (DMT)-based modulation scheme is employed, so that transmission over the frequencyselective channel may be decoupled into N independent subcarriers or tones. Both FDM and overlapping bandplans are considered. As overlapping bandplans require echo cancellation that is imperfect in practice, error that is introduced acts as a form of interference and is of concern. Echo cancellation error is modelled presuming a prevalent echo cancellation structure utilizing a joint timefrequency LMS algorithm [10] is employed 1 . Using the terminology of [10], let m denote the LMS adaptive step size parameter. The "excess MSE" for a given tone is modelled [15,Eqn. 12.74] as proportional to the product of the LMS adaptive step size parameter m and the transmit power on that tone. The constant of proportionality is absorbed by definingb as the ratio of excess MSE to transmitted energy on a given tone.

Achievable Rate Region
This section discusses an achievable rate region for a DSL modem based on the preceding channel and system model. The following analysis applies to both upstream and downstream transmission. For specificity, the following refers to downstream transmission: first, consider the case where echo cancellation is employed. Denote the victim modem's downstream transmit power on tone n, n ∈ {1, . . . , N} as x n . Let element l, l ∈ {1, . . . , L} of the vector y (n) ∈ R 2L + denote the downstream transmit power of interfering modem l on tone n. Similarly, let element l, l ∈ {L + 1, · · · , 2L} of y (n) denote the upstream transmit power of interfering user l − L. Define element l, l ∈ {l, . . . , L} of the row vector h (n) ∈ R 2L + , as the FEXT power gain from interfering user l on tone n (necessarily, h (n) 0). Similarly, define element l, l ∈ {L + 1, . . . , 2L} of h (n) to be the NEXT power gain from interfering user l − L. Leth (n) ∈ R + denote the victim line's insertion gain on tone n (h (n) ≥ 0). Independent AWGN (thermal noise) with power s 2 n > 0 is present on tone n. Letb n denote the echo cancellation ratio on tone n as described above. Echo-cancellation error is treated as AWGN. Let G denote the SNR gap-to-capacity [4]. Then the following bit loading is achievable on tone n [4]: . (1) Observe that ifh (n) = 0, then it is necessarily the case that b n = 0, implying that tone n is never loaded. Thus, in the sequel,h (n) > 0 for all n ∈ {1, . . . , N} is considered without loss of generality by removing those tones with zero direct gain (h (n) = 0). Defining a n = G /h (n) , b n = Gb n /h (n) , and N n = G s 2 n /h (n) , and substituting: Because G ≥ 1, it follows that a n ≥ 0, b n ≥ 0, and N n > 0. When an FDM scheme is employed, NEXT and echo cancellation are eliminated because transmission and reception occur on distinct frequencies 2 . Consequently, b n = 0 (due to no echo cancellation) and h (n) l = 0 for all n, L + 1 ≤ l ≤ 2L (due to frequency division).

Game-Theoretic Characterization of the WCI
This section introduces and motivates the concept of the worst-case interference (WCI). Suppose that a "victim" modem desires to keep its data rate at some level. Such a scenario is commonplace as carriers widely offer DSL service at a fixed data rate. To this end, define the worst-case interference as being that interference which minimizes the maximum achievable data rate of the victim subject to the preceding system model. By construction, this rate is a lower bound to the rate achievable under any other interference profile. Although such a configuration may appear pathological, it will be shown numerically that such a situation is quite reasonable. Neither is assuming such coordination of the interferers unreasonable in practice as under "Level 2" DSM [2] [3], each collocated carrier may individually coordinate its own lines, or collocated equipment may be centrally controlled by a competing carrier. Channels may be estimated in the field, approximated by standardized models [4], and in the future, potentially published by operators [16]. 2 Effects arising from implementation issues that may lead to crosstalk between upstream and downstream bands are not explicitly considered.

Formalization of the WCI Game
Consider the following two-player game: let Player 1 control the spectrum allocation of victim modem, and Player 2 control the spectrum allocations of all the interfering modems. Referring again to downstream transmission for specificity, let the total (sum) downstream power of the victim modem be upper bounded by The victim modem is also subject to a positive power constraint on each tone, x CAP x . Note that this constraint may be made redundant by setting e.g. CAP x 1P x . The requirement that CAP x 0 is without loss of generality by disregarding all unusable tones n for which CAP x n = 0. Similarly for Player 2, consider per-line power constraints 0 ≺ P y ≺ ¥ , and individual-tone power constraints on each tone CAP y,n 0; any power constraints equal to zero may be equivalently enforced by zeroing respective element(s) of {h (n) }. Thus the total downstream power of the l th interfering modem l ∈ {1, . . . , L} is upper bounded by the l th element of P y ∈ R 2L ++ , and the total upstream power of interfering modem l is upper bounded by element l + L of P y . Each interfering modem also has a power constraint on each tone, so that y (n) CAP y,n for all n.
The strategy set of Player 1 is the set of all feasible power allocations for the victim modem, S 1 = {x : 0 x CAP x , 1 T x ≤ P x }, and the strategy set of Player 2 is the set of all feasible power allocations for the interfering modems, S 2 = {[y (1) , . . . , y (N) ] : 0 y (n) CAP y,n , n = 1, . . . , N, [y (1) , y (2) , . . . , y (N) ]1 P y }. Define S = S 1 × S 2 . This is a strictly competitive or zero sum two-player game (S 1 , S 2 , J) where the objective function J : S → R + is defined to be the achievable data rate of the victim user: The game G = (S 1 , S 2 , J) is defined to be the Worst-Case Interference game. This condition immediately implies the claim that Player 1's rate at a Nash equilibrium of G lower bounds the achievable rate with any other feasible interference profile. This bound also extends to other settings: in the noncooperative IW game [17], a (possibly non-unique) Nash equilibrium is known to always exist in pure strategies; this condition again yields a rate lower bound at every Nash equilibrium of the IW game for the line corresponding to Player 1.

Derivation of Nash Equilibrium Conditions
The following result establishes the convex-concave property of the objective function.
Theorem 1 If a ≥ 0, b ≥ 0, g > 0, h 0, and a , b , g , h are bounded, then the function g : is strictly concave in x and is convex in y.
Proof. It is first claimed that f : is convex in h and strictly concave in x. Observe that f is continuous and twice differentiable, thus this follows [18] since for all (x, h ) ∈ R + × R + , ¶ 2 f ¶ h 2 ≥ 0 and ¶ 2 f ¶ x 2 < 0. For all (x, y) ∈ R + × R 2L + , it must be that h T y ≥ 0. Thus g(x, y) = f (x, h T y). By the affine mapping composition property [18], it follows that g(x, y) is convex in y and strictly concave in x.

Theorem 2 A Nash equilibrium (possibly not unique) of G always exists. Furthermore under FDM, if CAP x n ≥ P x for all n, then the optimal strategy of Player 1 is given by water-filling using a modified water level.
Proof. Because S 1 ⊂ R N and S 2 ⊂ R 2LN are closed and bounded, by Heine-Borel they are both compact. Also, the objective is a composition of continuous functions, and hence continuous. It follows from Theorem 1 and the separability of J over tones that J is concave in x and convex in [y (1) , . . . , y (N) ]. The result [19,Thm. 4.4] may therefore be applied to conclude that a pure-strategy saddle point exists. As a saddle point exists in pure strategies, the game has a value [19,Thm. 4.1], which shall be denoted as R * . Thus: The condition CAP x n ≥ P x ensures that the per-tone constraints are trivially satisfied whenever the power constraint (P x ) is. Evaluating the righthand side of (5), if b n = 0 (from FDM assumption) then: The optimization problem (6) is seen to be a single-user rate maximization with parallel Gaussian channels [13], and hence the (modified) waterfilling spectrum is optimal and unique. In particular, the modified AWGN noise level on tone n is seen to be a n h (n) y (n) + N n . This is the same modified noise level used in the rate-adaptive IW algorithm [4]. The following two theorems 3 characterize the structure of the set of all Nash equilibria of G .

Theorem 4 If the FDM condition is satisfied, then the set P of all Nash equilibria of the WCI game G is a polytope.
While solving for Player 1's strategy given Player 2's can be simple waterfilling (Theorem 2), computing a Nash equilibrium is nontrivial. However, this optimization problem can be solved using standard optimization techniques such as the "Infeasible Start Newton method" [18, §10.3]. Logarithmic barrier functions are employed to enforce the positivity and power constraints, and a central path algorithm is used to compute R * to arbitrary accuracy [18]. Let the central path parameter be denoted by t ∈ R ++ and definẽ S 1 = int(S 1 ),S 2 = int(S 2 ), andJ :S 1 ×S 2 → R + , where: 3 The proofs are not given due to space constraints.

VDSL Upstream with Near-Far Effect
The WCI rate bound is first applied to an upstream VDSL scenario exhibiting the near-far effect. For this simulation, 19 × 300 m lines, 10 × 1200 m lines, and one line of varying length occupy the binder of 24 AWG twisted-pairs. The FTTEx M2 (998 FDM) bandplan is employed with HAM bands notched, and the usual PSD masks are removed. Tones below 138 kHz are disabled for ADSL compatibility. The FDM condition is satisfied for this configuration (b n = 0). For 10 −7 BER, assume coding gain of 3 dB, with 6 dB margin, thus G = 12.5 dB. Each line is limited to 14.5 dBm (sum) power (P x = 14.5 dBm, P y = 1 · 14.5 dBm).
This section examines a simple power backoff strategy in the form of power-constrained RA IW for Level 0-1 DSM. Though the use of RA IW is retained, an effect similar to fixed-margin (rateconstrained) IW [20] is induced by imposing various tighter sum power constraints. In particular, the variable-length line is set to length 300 m, and (sum) power back-off is imposed on all (20) 300 m lines with full power retained on the (10) 1200 m lines. By taking the victim line to be one of the 300 m lines, the 300 m WCI curve in Figure 1 is generated, yielding a lower bound to the achievable data rate for all 300 m lines in the binder. The 1200 m WCI curve represents the case where the victim modem is instead taken to be one of the 1200 m lines. To compare standardized SSM techniques to DSM, the rates achieved using the SSM VDSL UBPO masking technique defined for the Noise A environment [21] are illustrated by dashed horizontal lines.
The results illustrate that a tradeoff exists between the rates of the short and long lines. Examining the 1200 m lines, the proposed technique improves both the RA IW-achieved and WCI bounds significantly up to approximately −30 dBm, with diminishing returns for further PBO as the 300 m line FEXT no longer dominates the interference profile. However, further PBO further decreases the achievable rates of the 300 m lines, as expected. The WCI bound is again fairly tight. Thus by employing such a simple PBO scheme with Level 1 DSM, one can dynamically control the tradeoff between short and long lines to best match desired operating conditions, i.e. operating with guaranteed ≈ 4 MBPS on the 1200 m lines and ≈ 7.75 MBPS on the 300 m lines. In this example, the SSM technique achieves approximately the same performance as this simple DSM technique at one tradeoff point (≈ −22 dB PBO).

ADSL Downstream with Remote Terminals (RT's)
The WCI rate bound is also applicable to ADSL. For this simulation, 25 ADSL lines are located 2000 m from a fiber-fed RT 4000 m from the CO. Additonally, 5 × 5000 m lines are present in the binder. The FDM ADSL standard [22] parameters are assumed. As in the VDSL simulations, G = 12.5 dB. Each line is limited to 20.4 dBm downstream power (P x = 20.4 dBm, P y = 1 · 20.4 dBm), and the standard PSD masks are neglected.
A well-known problem of such configurations is that the signal from the CO to the non-RT (7000 m) modems will be saturated by FEXT from the RT lines. As in the VDSL example, the efficacy of (sum) power backoff for the RT lines as a means of improving the rate of the CO lines is studied. Figure 2 shows the dependence of rates on the level of power backoff (relative to 20.4 dBm) for the RT lines. For comparison, the horizontal lines represent the performance obtained by SSM with the standardized PSD masks.
The WCI bound is reasonably close to actual power-controlled RA IW performance on both RT and CO lines. As in VDSL, a wide range of useful operating points may be attained; for example, it is possible (through proper power control) to guarantee 3 MBPS service on all lines, whereas this rate point was far from feasible with SSM or with full-power rate-adaptive IW. However without any power backoff, the performance of RA IW and the WCI bound are near that of SSM, showing the key role of power control in obtaining DSM gains in this setting.

CONCLUSION
This paper has studied the worst-case interference encountered when deploying Level 0-2 DSM techniques for next-generation DSL. A game-theoretic analysis has shown that under mild conditions, a pure-strategy Nash equilibrium exists in the WCI game, and can be computed using standard optimization techniques. The Nash equilibrium provides a useful lower bound to the achievable rate for a DSL modem employing DSM under any power-constrained interference profile. Furthermore, the structure of the Nash equilibrium reveals that for FDM systems, IW is optimal in a maxi-min sense.
The WCI bound was applied to a Level 0-1 upstream near-far VDSL scenario and found to be numerically tight. The utility of a simple DSM UPBO strategy employing RA IW was compared to SSM UPBO, were it was found that control of rate trade-offs is possible with DSM, which may allow significantly preferable operating rates. A similar tradeoff was observed in RT ADSL systems, where CO line performance benefits significantly from proper power control. These results suggest that the parameter of transmit power is important to DSM performance, in the sense that proper power control can beget large performance gains in this setting.