 Research
 Open Access
 Published:
Dynamic partial crosstalk cancellation resource allocation algorithms for DSL access networks
EURASIP Journal on Advances in Signal Processing volume 2012, Article number: 150 (2012)
Abstract
Earlier work on crosstalk mitigation techniques for DSL access networks has focused on physical layer transmit rate maximization or transmit power minimization through static resource allocation, i.e., static allocation of transmit power and/or computational complexity to the individual user in the network. However, such static resource allocation does not allow to consider upperlayer metrics such as network throughput, stability and delay performance. In this article, we develop a set of dynamic resource allocation algorithms for linear zeroforcing partial crosstalk cancellation that allow to include these upperlayer metrics, so as to dynamically allocate computational complexity to the individual users. A first algorithm focuses on preserving dynamic transmission queueing stability while maximizing the transmit rates. This algorithm is then extended towards budget adaptive algorithms, which improve resource efficiency, so as to obtain a tradeoff between delay performance and resource consumption. The improved stability and resource efficiency of the proposed algorithms are verified by simulations.
Introduction
Digital subscriber line (DSL) technology is a popular wireline broadband access technology with a more than 60% market share worldwide[1]. However, electromagnetic coupling between copperlines in the same binder, also referred to as crosstalk is known to result in a huge performance degradation in DSL access networks. To tackle the crosstalk problem, one can resort to two types of crosstalk mitigation techniques: (1) dynamic spectrum management (DSM), also referred to as spectrum balancing, which optimizes the transmit power spectra of the individual users in the network, to reduce the degradation caused by crosstalk. Various DSM algorithms have been developed, including centralized algorithms[2–4], distributed algorithms[5, 6], and autonomous algorithms[7, 8]. (2) Crosstalk cancellation, which is also referred to as vectored DSL or signal coordination, and includes upstream crosstalk cancellation and downstream precoding or precompensation. These techniques remove the crosstalk between the users through digital signal processing (DSP). Vectored DSL is seen as a very promising technique, and is subject of a standardization procedure of the international telecommunication union (ITU)[9, 10]. The vectored DSL system has been studied in[11–16]. In[12–16] simple linear zeroforcing crosstalk cancellation schemes have been proposed that reduce the crosstalk cancellation computational complexity by only removing the dominant crosstalk in the system. This is also referred to as partial crosstalk cancellation (PCC).
Considerable research on crosstalk mitigation techniques has been devoted to the maximization of physical layer transmit rates or the minimization of transmit powers[17]. Next to these standard objectives, other quality of service (QoS) objectives should also be considered. For instance, delay performance is a very important objective for different broadband scenarios: the impact of transmission delay on delaysensitive applications in next generation access networks, e.g., IPTV and online gaming, is studied in[18, 19].
Considering the data transmission between the access node (AN) and the customer premises equipment (CPE), there are four types of delay: (1) processing delay: the time consumed to process the data overhead. (2) Queueing delay: the time that the data sits in the transmission queue. (3) Transmission delay: the time to convert the data into an electrical signal and to feed it into the copperline. (4) Propagation delay: the time for the signal to propagate through the copperline. The processing delay and transmission delay depend on the processing capability of the chipset, and the propagation delay is related to the physics of the copperline. In this article we focus on the problem of controlling the queueing delay through dynamic PCC resource allocation.
Existing DSL physical layer optimization techniques generate a static resource allocation, for instance, statically allocating transmit power and/or computational complexity to the individual users. And these techniques focus on basic physical layer metrics, such as transmit rates and transmit power for the individual users. One shortcoming of such static allocation is that users are assumed to have an infinite data workload. This is however not true in practice, where users indeed have a finite data workload. Furthermore, when a user has no data to transmit, it should be allocated with as few resources as possible. A static system model does not allow to study the network throughput statically and delay performance. Therefore we extend the system model with data queues for all users, and show how this layered system model allows to study and design dynamic resource allocation algorithms that can significantly improve the performance of the DSL network.
A similar system model is also used with DSM in[20]. Queueing proportional scheduling (QPS)[21] provides good performance in the case of broadcast channel with sum transmit power constraint and superposition code at the transmitter together with successive interference cancellation at each receiver. However in DSL networks each user has an individual power constraint. The possibility of integrating QPS with DSL networks is discussed in[22]. In this article we focus on the linear zeroforcing PCC[12, 13], and develop a set of dynamic resource allocation algorithms. An initial framework was presented in our work[23], but these results are significantly extended in this article. More specifically, the contribution can be summarized as follows: A first algorithm focuses on preserving transmission queueing stability while maximizing the transmit rates. The impact of channel state information (CSI) uncertainty and nonoptimal resource allocation update rate to the algorithm is studied. We also propose an algorithm to reduce the resource allocation complexity by the frequency selectivity of the DSL channel. The framework is then extended towards budget adaptive algorithms, which improve resource efficiency, and optimize the resource subject to a delay performance target, so as to obtain a tradeoff between delay performance and resource consumption. The improved stability and resource efficiency of the proposed algorithms are verified by simulations.
The article is organized as follows: Section “System model” introduces the layered system model. Maxweight PCC algorithm is proposed in Section “Maxweight PCC”, which is a dynamic PCC resource allocation algorithm that focuses on preserving the dynamic transmission queueing stability. In Section “Features of MWPCC” some features of the MWPCC are discussed, including its robustness against channel uncertainty, the frequencyselectivity of the dynamic resource allocation, and the impact of the resource allocation update rate. In Section “Budget adaptive MWPCC” a set of budget adaptive MWPCC algorithms is developed, which relax the resource budget constraint and consequently improve the resource efficiency. Two extensions of the budget adaptive MWPCC are then proposed, which can realize a specific delay performance target, with respect to the system delay or individual user delay. Section “Simulation results” contains simulation results, that demonstrate the improved stability and the tradeoff between delay performance and resource consumption of the proposed algorithms. Conclusions are given in Section “Conclusion”.
System model
Physical layer resource allocation
The DMT based DSL system considered here consists of N users, where each user transmits over K orthogonal tones. We assume that accurate CSI is available at the AN. The transmission channel model on tone k is given as follows:
Here the vector${\overrightarrow{x}}_{k}={[{x}_{k}^{1},\dots ,{x}_{k}^{N}]}^{T}$ denotes the transmit signal from N users on tone k. The vectors${\overrightarrow{y}}_{k}$ and${\overrightarrow{z}}_{k}$ have the same structure as${\overrightarrow{x}}_{k}$, where${\overrightarrow{z}}_{k}$ denotes the additive noise vector, which consists of thermal noise and other background noises, and${\overrightarrow{y}}_{k}$ denotes the received signal vector. H_{ k } is an N×N matrix, whose element${h}_{k}^{n,m}$ represents the channel coefficient from user m’s transmitter to user n’s receiver.
We consider linear zeroforcing PCC for upstream communication and precoding for downstream communication, as introduced in[12, 13]. Both upstream crosstalk cancellation and downstream precoding work under the same principle, jointly referred to here as PCC. When a crosstalk canceller tap is deployed on a specific tone from a disturber user to a victim user, the corresponding crosstalk will be removed. Then the resulting bitloading on tone k of user n is as follows[14]:
with:${c}_{k}^{n,m}\in \{0,1\},\forall m\ne n$, where${c}_{k}^{n,m}=1$ if the crosstalk from user m to user n on tone k is removed, and${c}_{k}^{n,m}=0$ if the crosstalk from user m to user n on tone k is not removed,${s}_{k}^{n}$ and${\sigma}_{k}^{n}$ denote the transmit power and the noise power of user n on tone k. Υ refers to the gap to capacity. Throughout this article we assume a fixed power spectral density (PSD) for each user, i.e., fixed${s}_{k}^{n}$, ∀n k. When all the crosstalk seen by user n on tone k is cancelled, by allocating N−1 crosstalk canceller taps, the maximum bitloading is achieved, which is given as follows:
while the minimum bitloading corresponds to the case when no crosstalk is cancelled:
For user n, the transmit rate is:
where f_{ s }denotes the symbol rate. The maximum transmit rate of user n is calculated as below:
Partial crosstalk cancellation is seen to encompass a particular resource allocation, when a number of crosstalk canceller taps, i.e., computational complexity, is allocated to the individual users. The crosstalk canceller taps, as specified by${c}_{k}^{n,m},\forall m\ne n$, are constrained to a crosstalk canceller tap budget for all users in the system, denoted by C^{total}. The PCC resource consumption is thus constrained as follows:
where C^{Full} denotes the number of crosstalk canceller taps for full crosstalk cancellation, i.e.,
By distributing the crosstalk cancellers taps to different users on different tones, we can obtain different transmit rate vectors$\overrightarrow{R}={[{R}^{1},\dots ,{R}^{N}]}^{T}$. The physical layer rate region then characterizes the tradeoff between user transmit rates, subject to a specific crosstalk canceller tap budget C^{total}. It can be defined as follows,
Definition 1
(Physical layer rate region). The physical layer rate region $\mathcal{R}\subset {\mathbb{R}}_{+}^{N}$ is constructed as the finite set of all achievable transmit rate combinations:
where$C\left(\overrightarrow{R}\right)$ is the number of crosstalk canceller taps consumed when the transmit rate vector$\overrightarrow{R}$ is generated.
Dynamic transmission queueing system
For a realistic DSL scenario, the data workload represents the user behavior, and can be modeled as a timeslotted system, indexed by t. A finite firstinfirstout (FIFO) data queue is associated to each user, whose output is defined by the physical layer transmit rate R^{n}(t) and whose input is modeled as a random data arrival process A^{n}(t) with expected value$\mathbb{E}\left[{A}^{n}\right(t\left)\right]={\lambda}^{n}$. Moreover, we choose the time slot to be sufficiently small, such that A^{n}(t) is bounded to a constant ω^{n}, so that A^{n}(t) ≤ ω^{n},∀t ≥ 0. In the rest of the article, the vector$\overrightarrow{A}={\left[{A}^{1}\right(t),\dots ,{A}^{N}(t\left)\right]}^{T}$ will be defined as the Arrival process, and its expectation$\overrightarrow{\bigwedge}={[{\lambda}^{1},\dots ,{\lambda}^{N}]}^{T}$ will be defined as the Mean arrival rate vector.
Q^{n}(t) denotes the queue length of user n at time slot t, and we adopt a widely used model for queue length update[24–26]. For each time slot, the queue length of user n is updated as:
where, x^{+} = max(x,0).
Intuitively, the longer the queue, the longer the data waits in the queue. In an extreme case, if the queue length grows to infinity, not only the transmission stalls, but also the queueing data may cause a memory overflow in the system buffer. A static resource allocation cannot react when the queues of particular users grow. By dynamically allocating the physical layer resource based on the instantaneous queueing status, a high priority can be given to the users with a long queue, so as to improve the delay performance.
Dynamic transmission queueing stability
Our first goal is to prevent the queue lengths Q^{n}(t) from growing to infinity. When all the components of a dynamic system remain finite, we say such a system is stable. The stability of the transmission queueing system is then defined as follows:
Definition 2
(Dynamic transmission queueing stability). A dynamic transmission queueing system is called stable, if the following is satisfied:
Calculating how long exactly the data stays in the queue is not possible, due to the random arrival data A^{n}(t) and the timevarying transmit rate R^{n}(t). In this article, the time average of the total queue lengths of all users is used as a metric for the system delay performance:
Definition 3
(System delay). The system delay Ψ of a dynamic transmission queueing system is defined as:
Constrained by the physical layer resources, the dynamic transmission queueing system will not be able to stabilize an arrival process with an arbitrarily large mean arrival rate vector. We define the set of all mean arrival rate vectors [λ^{1},…,λ^{N}]^{T}, that can be stabilized, as the throughput region${\overrightarrow{\bigwedge}}^{\text{Throughput}}$.
Definition 4
(Throughput region). The throughputregion${\overrightarrow{\bigwedge}}^{\mathit{\text{Throughput}}}\subset {\mathbb{R}}_{+}^{N}$of a dynamic transmission queueing system is the set of all mean arrival rate vectors for which there exists a resource allocation algorithm stabilizing the system.
Intuitively, if the mean arrival rate vector$\overrightarrow{\bigwedge}$ is located in the physical layer rate region, there must be a transmit rate vector$\overrightarrow{R}$ larger than$\overrightarrow{\bigwedge}$, so that the queue cannot grow to infinity. More specifically, in[24], the throughput region is characterized as: ⋀^{Throughput} = convexhull($\mathcal{R}$), where$\mathcal{R}$ is the physical layer rate region.
Maxweight PCC
In this section we propose a first dynamic resource allocation algorithm, which will be referred to as MWPCC. This algorithm dynamically allocates the physical layer resources, i.e., the crosstalk canceller taps, based on the instantaneous queue lengths.
It is noted that with PCC such as in[12, 13], the crosstalk canceller taps are allocated at system startup, and this allocation then remains fixed during runtime. Such a static resource allocation corresponds to a point on the boundary of the rate region for a given crosstalk canceller tap budget C^{total}, and generates a rectangular throughput region which is only a part of the rate region. For a twouser scenario, the rate region and the rectangular throughput region of a static resource allocation are shown in Figure1. Therefore we propose a dynamic resource allocation approach, so as to reach all points of the rate region, i.e., to maximize the throughput region.
Partial crosstalk cancellation as a static resource allocation algorithm, relies on the following weightedsum optimization problem:
where C^{⋆} is the optimal crosstalk canceller allocation, and the W^{n}is the weight or priority given to user n.
Our objective is to preserve the dynamic transmission queueing stability under the dynamic transmission queueing model (5). Intuitively, a user with a long queue should get a high priority in the dynamic resource allocation. In the maxweight (MW) algorithm[24], the instantaneous queue lengths are used to represent the priority of the users in the resource allocation. Adopting this in the PCC context leads to the MWPCC algorithm defined as follows.
Definition 5
(MWPCC). For each time slot, the optimal resource allocation of the PCC is computed as:
Remark 1
By applying MWPCC, the throughput region is maximized to the convex hull of the rate region for the given resource budget C^{total}. When the mean arrival rate vector$\overrightarrow{\bigwedge}$is strictly interior to this throughput region, the transmission queues will not grow to infinity[24].
To dynamically allocate the physical layer resources based on the instantaneous queueing status, problem (8) needs to be solved for each time slot. We use a Lagrange dual decomposition approach to solve the optimization problem efficiently[14], by which the budget constraint (3) is moved into the objective function together with a Lagrange multiplier π ≥ 0 as follows:
The detailed description of the MWPCC algorithm with dual decomposition is presented in Algorithm 1. In the inner loop, the Lagrange multiplier Π is fixed, and the problem is decoupled over tones[14]. Furthermore, unlike in spectrum balancing, allocating more resources to a particular user, i.e., deploying more crosstalk canceller taps, will not cause additional crosstalk to other users. This makes a further decoupling over the users possible. Finally, since the largest crosstalk is to be removed first, with an ordering based on the crosstalk magnitudes[14], the pertone search space is dramatically reduced from (2^{N−1})^{N} to N−1, which can be easily covered by an exhaustive search. In the outer loop, the Lagrange multiplier Π is updated by a subgradient approach with an adaptive stepsize δ as presented in[27].
Algorithm 1 MWPCC
For each time slot:
while C ≠ C^{total}
for n = 1 to N
for k =1 to K
${C}_{k}^{n\star}\phantom{\rule{0.3em}{0ex}}=\phantom{\rule{0.3em}{0ex}}{\text{argmax}}_{\{{c}_{k}^{n,m},\forall k,m,m\ne n\}}{Q}^{n}\left(t\right){b}_{k}^{n}\phantom{\rule{0.3em}{0ex}}\Pi \phantom{\rule{0.3em}{0ex}}\sum _{m=1,m\ne n}^{N}{c}_{k}^{n,m}$
end for
end for
update Π
end while C converges to C^{total}
Update the queue lengths by (5)
Features of MWPCC
In this section we investigate three important features of MWPCC. From these features we will see that MWPCC offers far more than a basic function of preserving dynamic transmission queueing stability.
Robustness against channel uncertainty
In the system model, we assume that perfect CSI is available. For a practical vectored DSL system, the CSI is acquired at system startup, and is continuously tracked during runtime at low speed due to the quasistatic nature of the DSL channels[28]. This process generally leads to CSI uncertainty. Furthermore, ON/OFF events of alien crosstalk, i.e., crosstalk from uncoordinated users, during runtime can also change the CSI significantly. When an alien crosstalker begins to interfere with the coordinated users, the physical layer performance of the DSL system may be severely degraded. An exemplary rate region of PCC under channel uncertainty is given in Figure1.
A framework of dynamic resource allocation under CSI uncertainty is presented in[29]. For a system with CSI uncertainty, the throughput region is reduced, but any mean arrival rate vector located inside the reduced throughput region is still stabilizable by the MW algorithm.
To observe the performance of MWPCC under the CSI uncertainty, a set of simulations is shown in the Section VI. The result conforms to the conclusion of[29], that the stability of the queues can be preserved by MWPCC.
Frequency selectivity of resource allocation
In MWPCC, dynamic weights are assigned to the users, and this leads to a dynamic allocation of the crosstalk canceller taps to the users. Observing the crosstalk canceller taps allocation over the tones during a long term simulation, it is seen that this allocation exhibits some type of frequency selectivity.
We consider a fouruser upstream VDSL2 scenario, with two long lines of 1,500 m (User 1 and 2) and two short lines of 900 m (User 3 and 4), which are all connected to the same AN. The crosstalk canceller budget is set to 30% of full cancellation, i.e., C^{total}=0.3×C^{Full}. Observing the crosstalk canceller taps allocation on individual tones, we find that for some tones, the allocation is rarely changed, i.e., the resource allocation for these tone is relatively static.
Figure2 shows the average number of crosstalk canceller taps allocated to individual tones over 1,000 time slots. From this figure, we observe that:

Some tones are allocated with an approximately integer average number of the crosstalk canceller taps, namely the tones with the relatively static resource allocation.

Among these static tones, some tones are always allocated with crosstalk canceller taps, whilst others are never allocated with any crosstalk canceller taps.

Tones in the middle frequency range are always allocated with crosstalk canceller taps. The resource allocation for the long line targets mostly lower frequencies, whilst for the short line both higher and lower frequencies are targeted.
This frequency selectivity of the resource allocation originates from the nature of the DSL channel. By removing the 30% most dominant crosstalk, 80 to 90% of the transmit rate improvement of full crosstalk cancellation can be achieved[13]. Further increasing the crosstalk canceller tap budget will have little improvement on the transmit rates. Therefore the tones with dominant crosstalk are always allocated with crosstalk canceller taps. Removing the crosstalk on some of the remaining tones does not contribute much to the transmit rate, and hence these tones are always allocated with few crosstalk canceller taps.
Based on the above observation, we propose a partialdynamic MWPCC (PDMWPCC) resource allocation algorithm. In this algorithm, only a subset of the tones is dynamically allocated with crosstalk canceller taps, while the other tones have a static allocation. In this way the computational complexity of the resource allocation algorithm is reduced. First we define static tones, and dynamic tones.
Definition 6
(Static tones). The static tones will be allocated with a constant numbers of crosstalk canceller taps.
Definition 7
(Dynamic tones). The dynamic tones will be dynamically allocated with crosstalk canceller taps.
As a predefined parameter, we set α% of all tones to be dynamic tones. First, in a training phase at system startup, a dynamic allocation is obtained, as represented in Figure2. Then α% of the most dynamic tones will be set as dynamic tones. The rest of the tones will be set as static tones. In this way, the number of MWPCC inner loop is reduced from K to α% × K.
The simulation results of PDMWPCC show a nearoptimal performance compared to the MWPCC, where the gap to the optimal performance obviously depends on the choice of α.
Resource allocation update rate
In order to achieve optimal performance, the resource allocation should be updated at a sufficiently high rate, such that MWPCC can adapt sufficiently fast to the evolution of the queue lengths. Since the arrival processes are modeled as random processes, the optimal update rate, should be chosen to correspond to the time duration, in which the random processes can be considered as stationary. In this way, the instantaneous queue lengths accurately represent the dynamic behavior of the arrival processes.
In the current DSL system, the symbol rate is 4,000 symbols per second, thus the largest possible update rate is 0.25 ms. However, next to the computational complexity, the signaling overhead at such a high update rate will be enormous. Consider an AN with MWPCC implementation. The resource allocation update requires CSI and instantaneous queue length information. For the downstream, the queue length information is available at the AN, but for the upstream, the queue lengths at the user side have to be reported from the CPEs to the AN.
For the upstream, the CSI can be updated at the AN, but for the downstream, updated CSI has to be reported from the CPE to the AN. From the implementation point of view, we thus look for a tradeoff between the optimal resource allocation update rate and the signaling overhead.
Algorithm 2 Partialdynamic MWPCC
Only for the system startup:
Training: Determine the α% most dynamic tone. And set static allocation for the rest of tone (static tone).
For each time slot:
while C ≠ C^{total} do
for n = 1 to N do
for k = 1 to K do
if Tone k is dynamic then
${c}_{k}^{n,\mathit{\text{opt}}}=\underset{\{{c}_{k}^{n,m},\forall k,m,m\ne n\}}{\text{argmax}}{Q}^{n}\left(t\right){b}_{k}^{n}\Pi \sum _{m=1}^{N}{c}_{k}^{n,m}$
end if
end for
end for
update Π
end while C converges to C^{total}
update the queue lengths by (5)
Simulation results will show that the delay performance under reduced update rate is nearoptimal, the negative effect of reducing the update rate being minor, and that the transmission stability is not affected.
Budget adaptive MWPCC
For a fixed crosstalk canceller budget C^{total}, for any stabilizable mean arrival rate vector, the resulting instantaneous transmit rate vector of MWPCC always lies on the boundary of the rate region$\mathcal{R}$. When the mean arrival rate vector is close to the boundary of the rate region, stability is preserved but the delay performance may be poor. When the mean arrival rate vector is far from the boundary of the rate region, the delay performance may be much better. The MWPCC is then found to lack flexibility in its resource allocation as it always allocates all the available resources. In this section we propose a budget adaptive MWPCC, in which instead of a fixed crosstalk canceller budget, an instantaneous budget is determined by the instantaneous queue lengths.
Minimum budget for stability
Considering different crosstalk canceller tap budgets smaller than a budget C^{total}, the set of all possible throughput regions can be constructed$\overrightarrow{\Gamma}=\left\{{\overrightarrow{\bigwedge}}^{\text{Throughput}}\right(C):C\le {C}^{\text{total}}\}$. For any stabilizable mean arrival rate vector, there must be at least one throughput region from$\overrightarrow{\Gamma}$ that contains this vector. The throughput region with smallest crosstalk canceller tap budget, that can stabilize this mean arrival rate vector, has the shortest distance between the mean arrival rate vector and the boundary of the throughput region. A similar concept for transmit energy is introduced in[25, 26].
Definition 8
(Minimum budget for stability). For a mean arrival rate vector $\overrightarrow{\bigwedge}\in \mathcal{R}$ (4), the minimum required crosstalk canceller tap budget for stability C ^{least} is defined as:
where$\overrightarrow{R}$is the resulting transmit rate vector when the crosstalk cancellation is defined by the${c}_{k}^{n,m}$s.
The minimum budget preserves stability, but leads to the poorest delay performance for the given mean arrival rate vector. In other words, any crosstalk canceller tap budget larger than this minimum budget can provide a better delay performance.
Budget adaptive MWPCC
Based on the above statement, we propose a budget adaptive MWPCC (BAMWPCC) algorithm. In this algorithm, the instantaneous crosstalk canceller tap budget$C\left(t\right)=\sum _{k=1}^{N}\sum _{n=1}^{N}\sum _{m=1,m\ne n}^{N}{c}_{k}^{n,m}$ in time slot t is determined by the instantaneous queue lengths. We define a cost constant V , and introduce a penalty term −V×C(t) into (8). For each time slot, we allocate the crosstalk cancellation taps according to the following optimization problem:
where C^{total} is the maximum crosstalk canceller tap budget. In order to achieve the largest possible throughput region, in the rest of the article we choose C^{total} = C^{Full}.
In this optimization problem, the weighted transmit rate sum is penalized by the crosstalk canceller tap budget, so that the instantaneous transmit rate vector is no longer constrained to lie on the rate region boundary of a fixed budget. When the queues are short, the penalty term (the second term in the right hand side of (10)) is more dominant than the first term, and as a result only few crosstalk cancellers taps will be allocated. As the queues grow, the first term could take over from the penalty term, and more crosstalk cancellers taps will be allocated. In this way, the resource budget is flexible and efficient, and dependent on the instantaneous queue lengths.
The penalty term is parameterized by V . For the same arrival process, if V is small, the penalty is insignificant, and results in high transmit rates and a good delay performance. If V is large, then the crosstalk canceller tap budget is tightened, and the delay performance may be poor. Hence a tradeoff between delay performance and resource consumption is realized.
Remark 2
For any positive number V, the dynamic transmission queueing system is always stabilized, as long as the mean arrival rate vector is strictly interior to the throughput region corresponding to the maximum crosstalk canceller tap budget C^{Full}. A proof of this is given in the Appendix.
Remark 3
The cost constant V is not necessarily positive. If the cost constant V is not positive, the objective function (10) is monotonically increasing with respect to the crosstalk canceller tap budget. This leads to full crosstalk cancellation, i.e., C(t) = C^{Full}.
Algorithm 3 BAMWPCC
For each time slot:
Update the queue lengths by (5)
Total queue length tracking BAMWPCC
We introduce a further extension of the BAMWPCC algorithm. A different choice of the cost constant V is known to result in a different delay performance. However, the relation between the delay performance and the resource consumption is nonanalytic. In order to achieve a specific delay performance, the cost constant V is replaced by a dynamic cost index V(t), which is updated based on a “Total queue length”$\Psi \left(t\right)=\sum _{n=1}^{N}{Q}^{n}\left(t\right)$, as follows,
where Ψ^{target} is the target total queue length. δ is a constant stepsize, for which we choose a small positive number. After updating the cost index V(t), the remaining procedure is the same as BAMWPCC.
With this dynamic cost index V(t), the crosstalk canceller tap budget is regulated by the difference between the instantaneous and the target total queue length. Note that this algorithm is only able to track the target total queue length Ψ^{target}, but not precisely constrain to it.
The significance of this dynamic penalty term is that the highly coupled relationship between the delay performance and the resource consumption is bypassed.
Remark 4
If the transmit rates are always sufficiently large to transmit the whole queue before the new data arrives, the instantaneous total queue length is minimized and hence the longterm average of the total queue length is lower bounded by:
Hence, any Ψ^{target}smaller than this bound will result in negative V(t), and full crosstalk cancellation.
Algorithm 4 Total queue length tracking bAMWPCC
For each time slot:
Update V(t):
Update the queue lengths by (5)
Individual queue length tracking BAMWPCC
In the total queue length tracking BAMWPCC, all the users in the system are considered as a whole, and the individual delay performance of each user is not taken into account. Fairness between the users and the individual delay performance demands are not considered. Alternatively, we set a target queue length Q^{n,target} for each user, and correspondingly a dynamic cost index V^{n}(t) for each user. In each time slot, the dynamic cost index V^{n}(t) of each user is updated as follows,
where the stepsize δ is a small positive number. After updating the cost index V^{n}(t),∀n, the remaining procedure is the same as BAMWPCC, except that the penalty term$\sum _{n=1}^{N}\left({V}^{n}\right(t\left){C}^{n}\right(t\left)\right)\left({C}^{n}\right(t)=\sum _{k=1}^{K}\sum _{m=1,m\ne n}^{N}{c}_{k}^{n,m})$, is computed in peruser fashion. As a result, the queue length of each user is always controlled towards the target queue length.
Remark 5
Similar to Remark 4, a target queue length Q^{n,target}smaller than$\mathbb{E}\left({A}^{n}\right)$, results in full crosstalk cancellation for user n.
Algorithm 5 Individual queue length tracking BAMWPCC
For each time slot:
∀n: Update V^{n}(t):
Update the queue lengths by (5)
Simulation results
The simulations are performed for a VDSL2 upstream scenario with four users, two 1,500 m long lines (user 1 and 2) and two 900 m short lines (user 3 and 4), which are connected to the same AN. The diameter of the twisted pair lines is set to 0.5 mm. The coding gain is set to 3dB and the noise margin is set to 6 dB. The target error probability is 10^{−7}. The tone spacing Δ_{ f }is 4.3125 kHz and 2,786 tones ranging from 0 Hz to 12 MHz are used. The symbol rate f_{ s } is 4,000 Hz. We fix the transmit power at −60dBm/Hz on all the tones.
Performance of MWPCC
The arrival processes are randomly generated with a uniform distribution, whose mean arrival rate vector is close to the boundary of throughput region. The queue lengths and the achieved transmit rates are shown as a function of the time in Figures3 and4, respectively. We can see that the dynamic transmission queueing system is stabilized by the dynamic resource allocation.
In Figure5, the relationship between the system delay and crosstalk canceller tap budget is shown. The mean arrival rate vector is close to the throughput region boundary for a 30% crosstalk canceller tap budget. By increasing the budget from 30 to 40% and 50%, the system delay is improved.
We investigate a typical scenario of CSI uncertainty, where the channel gain H^{2} is degraded by the error in CSI. The resulting degradation in SNR has a Gaussian distribution over all the tones, with a mean value of −3 dB and variance of 1. In Figure6, we can see that the system delay is slightly larger then the system delay under perfect CSI, however, stability is still preserved.
To verify the robustness against alien crosstalk, we assume that the system starts with no alien crosstalk. In the first stage of Figure7, the dynamic transmission queueing system is stable. Then a 600 m user is added to the system, which introduces the alien crosstalk. Although the system delay increases rapidly, it converges to a new stable level. The MWPCC is thus seen to be robust against unknown alien crosstalk up to a certain degree.
The performance of the Partial Dynamic MWPCC algorithm is evaluated with two settings: allocation scheme (A) is a “conservative” one, where 85% of the tones are dynamic, and allocation scheme (B) is an “aggressive” one, where only 50% of the tones are dynamic. The resulting static tones are shown in Figure8. (The dynamic tones are not plotted.)
The delay performance of the Partial Dynamic MWPCC algorithm is given in Figure9, with the delay performance of the fully dynamic MWPCC as reference. The “conservative” scheme has a performance very close to the reference, whilst the “aggressive” scheme has a degraded performance, but stability is still preserved.
Finally we consider the effect of a nonoptimal resource allocation update rate. For reference, we adopt a 1 Hz resource allocation update rate as the optimal update rate, i.e. the arrival process is statistically timehomogenous within in the interval of one second. In nonoptimal algorithm, the time slot is expanded by a factor of 50, i.e., the resource allocation is updated only every 50 s. The resulting delay performance is shown in Figure10. Despite the fact that the arrival process is no longer statistically timehomogeneous within one time slot, the system delay is close to the optimal one.
Performance of BAMWPCC
In this section we investigate the performance of the budget adaptive algorithms. First we run simulations with two different mean arrival rate vectors, where one is inside the rate region of 30% crosstalk cancellation and the other is outside this rate region. In Figure11, we can see that the fixed budget (30%) MWPCC can only stabilize the arrival process with mean arrival rate vector inside the rate region (unstable procedure of the mean arrival rate vector outside the rate region not shown). With a randomly chosen cost constant V = 10, the BAMWPCC can stabilize both arrival processes, by adaptively tuning the instantaneous budget. On average, the BAMWPCC uses 22.7% of C^{Full} to stabilize the arrival process with mean arrival rate vector inside the rate region, and uses 33.1% of C^{Full} for the mean arrival rate vector outside the rate region. Therefore the BAMWPCC is more resource efficient than fixed budget MWPCC, when stabilizing the same arrival process. Moreover, the throughput region is flexible for BAMWPCC, by adjusting the crosstalk canceller tap budget.
To further exploit the resource efficiency of the BAMWPCC, we consider a scenario with two phases with different mean arrival rate vectors. In Figure12 two rate region contours, which are generated by 30% of C^{Full} (solid line) and 50% of C^{Full}(dashed line), and two corresponding mean arrival rate vectors, marked by the cross, are shown. The resulting distribution of the instantaneous transmit rate vectors are demonstrated as cloud (here V = 10). We can see that the transmit rates are no longer constrained by the fixed budget, and distributed around the mean arrival rate vector. When the mean arrival rate vector changes, the transmit rate vectors distribution adapts to the change.
The resource efficiency of the total queue length tracking BAMWPCC is demonstrated in Figure13. First we obtain a system delay for an arrival process with MWPCC as reference. Setting this total queue length as the target total queue length, the Total Queue Length Tracking BAMWPCC can reach the same delay performance, where the resource consumption is obviously lower than for MWPCC.
Conclusion
A dynamic PCC resource allocation algorithm has been proposed, referred to as MWPCC, which dynamically allocates crosstalk canceller taps so as to stabilize the dynamic arrival data of the system and to maximize the throughput region. Based on the frequency selectivity of DSL network channel, we proposed Algorithm 2, which can reduce the computational complexity of resource allocation, with a slight loss in delay performance. Budget adaptive algorithms (Algorithms 3, 4 and 5) have also been proposed, which not only achieve the same delay performance as MWPCC, but also dynamically adapt the crosstalk canceller tap budget so as to obtain a better resource efficiency. Algorithm 4 focuses on the delay performance target of the whole system, while Algorithm 5 further enables an explicit peruser delay performance target.
Appendix
BAMWPCC stability proof
We define the textitquadratic Lyapunov function and the Lyapunov drift of the dynamic transmission queueing system as follows,
Definition 9
(Quadratic Lyapunov function). The quadratic Lyapunov function of the dynamic transmission queueing system is defined as the quadratic sum of the instantaneous queue lengths:
Definition 10
(Lyapunov drift). The Lyapunov drift of the dynamic transmission queueing system is defined as the expectation of the difference of the quadratic Lyapunov function between two consecutive time slots:
Considering the dynamics of the queue lengths (5), we distinguish between two cases:
or
In (14), the transmit rate is larger than the previous queue length. If this is the case for all time slots and all users, then the expectation of the queue length of user n is equal to the mean arrival rate λ^{n}, which is bounded by ω^{n}. Thus the queue lengths will not go to infinity, and stability is preserved.
The stability proof focuses on the second case (15) as a worst case, where the queue may have residual data from the previous time slot. The resulting instantaneous queue length could be larger than the arrival data. We assume this is the case for at least one user at each time slot, i.e., at least one user’s queue length is growing. Then (5) is simplified to:
We expand the Lyapunov drift with (16) at time slot t:
Regardless of the time slot, the arrival rate of user n is bounded by ω^{n}, and the transmit rate is limited by the maximum transmit rate${R}_{\mathrm{max}}^{n}$ as defined in (2). We define a constant B to replace the first item on the right hand side of (17):
Also, A^{n}(t) is independent of Q^{n}(t), as the arrival process is not dependent on the instantaneous queue length Q^{n}(t), therefore we replace$\mathbb{E}\left[\right({A}^{n}\left(t\right)\left\overrightarrow{Q}\right(t\left)\right]$ with λ^{n}, and we obtain the following inequality from (17):
Then we remove the last term of the right hand side of (18), which is negative, and introduce the instantaneous penalty function −V × C(t) of the resource consumption into (18):
Then we remove the last term of the right hand side of (18), which is negative, and introduce the instantaneous penalty function −V × C(t) of the resource consumption into (18):
Suppose we have a vector$\overrightarrow{\epsilon}={[{\epsilon}^{1}{\epsilon}^{2}\dots {\epsilon}^{n}]}^{T}$ that satisfies λ^{n} + ε^{n}< ω^{n} and${\overrightarrow{\bigwedge}}^{\u2033}=\overrightarrow{\bigwedge}+\overrightarrow{\epsilon}\in {\overrightarrow{\bigwedge}}^{\text{Throughput}}$. From Theorem 8, there is a${C}^{\text{least},\epsilon}=\sum _{k=1}^{K}\sum _{n=1}^{N}\sum _{m=1,m\ne n}^{N}{c}_{k}^{n,m}$, that can stabilize${\overrightarrow{\bigwedge}}^{\u2033}$. We introduce C^{least,ε}into the right hand side of (19), and remove the negative term$V\mathbb{E}\left[C\right(t\left)\right\overrightarrow{Q}\left(t\right)\left]\right)$. Then we take the expectation over the distribution of$\overrightarrow{Q}\left(t\right)$:
As (20) is valid for all time slots, we sum it over all time slots t∈{0,1,…,T−1} and divide the sum by T:
The positive term$\frac{1}{T}\mathbb{E}\left[L\right(\overrightarrow{Q}\left(T\right)\left)\right]$ in the left hand side of (21) can be ignored. By manipulating (21) again, we obtain:
where ε_{min}=min(ε^{1},ε^{2},…,ε^{n}). The left side of (22) is the longterm average of the queue lengths, i.e., the system delay. It is bounded by the constants$B,V,\overrightarrow{\epsilon}$ and the initial status of$\overrightarrow{Q}\left(0\right)$. If the initial status$\overrightarrow{Q}\left(0\right)$ is not infinity, then the queue lengths will not grow to infinity, which proves the stability of BAMWPCC.
Remark 6
The upper bound for the system delay given in (22) is not a tight bound.
Remark 7
If the cost constant V is zero, the BAMWPCC is equal to MWPCC. Therefore the stability of MWPCC is also proved.
References
 1.
Mastrangelo T: Annual Market Outlook Update. 2008, Report 081120 v1 http://www.broadbandtrends.com
 2.
Cendrillon R, Yu W, Moonen M, Verlinden J, Bostoen T: Optimal multiuser spectrum balancing for digital subscriber lines. IEEE Trans. Commun 2006, 54(5):922933.
 3.
Cendrillon R, Moonen M: Iterative spectrum balancing for digital subscriber lines. IEEE International Conference on Communications (ICC) 2005, 19371941.
 4.
Yu W, Lui R: Dual methods for nonconvex spectrum optimization of multicarrier systems. IEEE Trans. Commun 2006, 54(7):13101322.
 5.
Tsiaflakis P, Diehl M, Moonen N: Distributed spectrum management algorithms for multiuser DSL networks. IEEE Trans. Signal Process 2008, 56(10):48254843.
 6.
Moraes R, Dortschy B, Klautau A, Riu J: Semiblind power allocation for digital subscriber lines. IEEE International Conference on Communications (ICC) 2008, 14201425.
 7.
Cendrillon R, Huang J, Chiang M, Moonen M: Autonomous spectrum balancing for digital subscriber lines. IEEE Trans. Signal Process 2007, 55(8):42414257.
 8.
Yu W, Ginis G, Cioffi J: Distributed multiuser power control for digital subscriber lines. IEEE J. Sel. Areas Commun 2002, 20(5):11051115. 10.1109/JSAC.2002.1007390
 9.
Oksmanm V, Schenk H, Clausen A, Cioffi J, Mohseni M, Ginis G, Nuzman C, Maes J, Peeters M, Fisher K, Eriksson PE: The ITUT’s new G.vector standard proliferates 100 Mb/s DSL. IEEE Commun. Mag 2010, 48(10):140148.
 10.
International Telecommunication Union, SelfFEXT Cancellation (Vectoring) for use with VDSL2 Transceivers ITUT Rec. G.993.5(G.Vector) 2009
 11.
Ginis G, Cioffi J: Vectored transmission for digital subscriber line systems. IEEE J. Sel. Areas Commun 2002, 20(5):10851104. 10.1109/JSAC.2002.1007389
 12.
Cendrillon R, Moonen M, Ginis G, van Acker K, Bostoen T, Vandaele P: Partial crosstalk cancellation for upstream VDSL. EURASIP J. Appl. Signal Process 2004, 2004: 15201535. 10.1155/S1110865704309273
 13.
Cendrillon R, Ginis G, Moonen M, van Acker K: Partial crosstalk precompensation in downstream VDSL. Elsevier Signal Process. Spec Issue Signal Process. Commun 2004, 84(11):20052019.
 14.
Vangorp J, Tsiaflakis P, Moonen M, Verlinden J, Ysebaert G: A dual decomposition approach to partial crosstalk cancelation in a multiuser DMTxDSL environment. EURASIP J. Adv. Signal Process 2007, 2007(37963):111.
 15.
Forouzan AR, Garth LM: Computationally efficient partial crosstalk cancellation in fast timevarying DSL crosstalk environments. EURASIP J. Appl. Signal Process 2007, 2007: 4242.
 16.
Pandey PK, Moonen M, Deneire L: MMSEbased partial crosstalk cancellation for upstream VDSL. IEEE International Conference on Communications (ICC) 2010, 15.
 17.
Tsiaflakis P, Yi Y, Chiang M, Moonen M: Green DSL: energyefficient DSM. IEEE International Conference on Communications (ICC) 2009.
 18.
Foglar A, Polig R: PlaNetS QoS Solution. 2007,.http://www.medeaplanets.eu/QoSsolution.php?page=home
 19.
Areizaga E, Foglar A, Elizondo AJ, Geilhardt F: Enabling broadband as commodity within access networks: a QoS recipe. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, vol. 6, (2009)
 20.
Tsiaflakis P, Yi Y, Chiang M, Moonen M: Throughput and delay of DSL dynamic spectrum management with dynamic arrivals. IEEE Global Telecommunications Conference(Globecom) 2008.
 21.
Seong K, Narasimhan R, Cioffi J: Queue proportional scheduling via geometric programming in fading broadcast channels. IEEE J. Sel. Areas Commun 2006, 24(8):15931602.
 22.
Cioffi J, Brady M, Pourahmad V, Jagannathan S, Lee W, Kim Y, Chen C, Seong K, Yu D, Ouzzif M, Mariotte H, Tarafi R, Ginis G, Lee B, Chung T, Silverman P, A Inc: Vectored DSLs with DSM: The road to Ubiquitous Gigabit DSLs, 2008.
 23.
Li B, Tsiaflakis P, Moonen M, Maes J, Guenach M: Dynamic resource allocation based partial crosstalk cancellation in DSL networks. IEEE Global Telecommunications Conference(Globecom) 2010.
 24.
Georgiadis L, Neely MJ, Tassiulas L: Resource allocation and crosslayer control in wireless networks. Found. Trends Netw 2006, 1: 1144.
 25.
Neely M: Energy optimal control for timevarying wireless networks. IEEE Trans. Inf. Theory 2006, 52(7):29152934.
 26.
Neely M, Modiano E, Rohrs C: Dynamic power allocation and routing for timevarying wireless networks. IEEE J. Sel. Areas Commun 2005, 23: 89103.
 27.
Tsiaflakis P, Vangorp J, Moonen M, Verlinden J, Van Acker K: An efficient search algorithm for the lagrange multipliers of optimal spectrum balancing in multiuser xDSL systems. IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) 2006, IVIV.
 28.
AlcatelLucent: G.vector: On the tracking speed required for changing crosstalk channels (update). ITUT SG15/Q4 RJ062 2007
 29.
Pantelidou A, Ephremides A, Tits A: A crosslayer approach for stable throughput maximization under channel state uncertainty. Wirel. Netw 2009, 15: 555569. 10.1007/s1127600700897
Acknowledgements
This research work was carried out at the ESAT Laboratory of the Katholieke Universiteit Leuven, in the frame of Concerted Research Action GOAMaNet, the ECFP6 project SIGNAL: Core Signal Processing Training Program, the Belgian Programme on Interuniversity Attraction Poles initiated by the Belgian Federal Science Policy Office IUAP P6/04 (DYSCO, ‘Dynamical systems, control and optimization’), Research Project FWO nr.G.0235.07 (‘Design and evaluation of DSL systems with common mode signal exploitation’) and IWT Project ‘iSEED: Innovation on stability, spectral and energy efficiency in DSL’ and IWT Project ‘PHysical layer and Access Node TEchnology Revolutions: enabling the next generation broadband network’ (PHANTER). Paschalis Tsiaflakis is a postdoctal fellow funded by the Research FoundationFlanders (FWO). This article has partly appeared in the proceeding of the IEEE Global Telecommunications Conference (GLOBECOM) 2010, Miami, Florida, Dec 2010.[23]
Author information
Affiliations
Corresponding author
Additional information
Competing interests
The authors declare that they have no competing interests.
Authors’ original submitted files for images
Below are the links to the authors’ original submitted files for images.
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 2.0 International License (https://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
About this article
Cite this article
Li, B., Tsiaflakis, P., Moonen, M. et al. Dynamic partial crosstalk cancellation resource allocation algorithms for DSL access networks. EURASIP J. Adv. Signal Process. 2012, 150 (2012). https://doi.org/10.1186/168761802012150
Received:
Accepted:
Published:
Keywords
 Time Slot
 Channel State Information
 Queue Length
 Delay Performance
 Resource Allocation Algorithm