Haythem Bany
email: haythem@yu.edu.jo

Salameh Marwan Krunz

Channel Assignment and Access Protocols for Spectrum-agile Networks with Single-Transceiver Radios

Keywords: Opportunistic Access, Cognitive Radio, Single-transceiver

Many spectrum access/sharing algorithms for cognitive radio networks (CRNs) have been designed assuming multiple transceivers per CR user. However, in practice, such an assumption may not hold due to hardware cost. In this paper, we address the problem of assigning channels to CR transmissions, assuming one transceiver per CR. The primary goal of our design is to maximize the number of feasible concurrent CR transmissions with respect to both spectrum assignment and transmission power. Energy conservation is also treated, but as a secondary objective. The problem is posed as a utility maximization problem subject to target rate demand and interference constraints. For multi-transceiver CRNs, this optimization problem is known to be NP-hard. However, under the practical setting of a single transceiver per CR user, we show that this problem can be optimally solved in polynomial time. Specifically, we present a centralized algorithm for the channel assignment problem based on bipartite matching. We then integrate this algorithm into distributed MAC protocols. First, we consider a single-hop CRN, for which we introduce a CSMA-like MAC protocol that uses an access window (AW) for exchanging control information prior to data transmissions. This approach allows us to realize a centralized algorithm in a distributed manner. We then develop a distributed MAC protocol (WFC-MAC) for a multi-hop CRN. WFC-MAC improves the CRN throughput through a novel distributed channel assignment that relies only on information provided by the two communicating users. We compare the performance of our schemes with CSMA/CA variants. The results show that our schemes significantly decrease the blocking rate of CR transmissions, and hence improves the network throughput.

Introduction

The widespread acceptance of the unlicensed wireless communication services and applications has significantly increased the demand for more transmission capacity. The unlicensed portions of the frequency spectrum (e.g., the ISM bands) have become increasingly crowded. At the same time, recent radio measurements conducted by the FCC and other agencies revealed vast temporal and geographical variations in the utilization of the licensed spectrum, ranging from 15% to 85% [1]. To overcome spectrum scarcity, cognitive radios have been proposed to allow opportunistic on-demand access to the spectrum [1,[START_REF] Bany Salameh | Channel Access Protocols for Multihop Opportunistic Networks: Challenges and Recent Developments[END_REF]. CR technology offers such opportunistic capability without affecting licensed primary radio (PR) users. Specifically, CR users access the available spectrum opportunistically by continuously monitoring the operating channels so as to avoid degrading the performance of PR users [START_REF] Bany Salameh | Channel Access Protocols for Multihop Opportunistic Networks: Challenges and Recent Developments[END_REF]. They should frequently sense their operating channels for active PR signals, and should vacate these channels if a PR signal is detected. In such an opportunistic environment, the crucial challenge is how to allow CR users to efficiently share (utilize) the available spectrum opportunities while improving the overall achieved throughput.

Several MAC protocols have been proposed for CRNs (e.g., [START_REF] Bany Salameh | MAC protocol for opportunistic cognitive radio networks with soft guarantees[END_REF][START_REF] Sabharwal | Opportunistic spectral usage: Bounds and a multi-band CSMA/CA protocol[END_REF][START_REF] Bany Salameh | Rate-maximization channel assignment scheme for cognitive radio networks[END_REF][START_REF] Yuan | Knows: Kognitive networking over white spaces[END_REF][START_REF] Bany Salameh | Cooperative adaptive spectrum sharing in cognitive radio networks[END_REF]). We refer the interested reader to our technical report [START_REF] Bany Salameh | Spectrum sharing with adaptive power management for throughput enhancement in dynamic access networks[END_REF] for an extensive overview of related works. Most of these protocols assume that each CR is equipped with multiple transceivers, which may not often be the case. In addition, these protocols are often based on a greedy channel assignment strategy, which selects the "best" available channel (or channels) for a given transmission [START_REF] Bany Salameh | MAC protocol for opportunistic cognitive radio networks with soft guarantees[END_REF][START_REF] Jain | A multichannel CSMA MAC protocol with receiver-based channel selection for multihop wireless networks[END_REF]. The best channel is often defined as the one that supports the highest rate. Hereafter, we refer to this strategy as the best multichannel (BMC) approach. As shown later, when the BMC approach is employed in a CRN, the blocking probability for CR transmissions increases, leading to a reduction in network throughput. In contrast, in our work, we consider a single half-duplex transceiver per CR user. Our goal is to maximize the number of concurrent feasible CR transmissions, and conserve energy as a secondary objective, with respect to both spectrum assignment and transmission power. For multitransceiver CRNs, this joint channel assignment and power allocation problem is known to be NP-hard [START_REF] Bany Salameh | Cooperative adaptive spectrum sharing in cognitive radio networks[END_REF][START_REF] Behzad | Multiple access protocol for power-controlled wireless access nets[END_REF]. However, for the single-transceiver case, we show that this problem can be optimally solved in polynomial time. Our optimization follows a "fall back" approach, whereby the secondary objective is optimized over the set of feasible channel assignments that are found to be optimal with respect to the primary objective. Contributions: The contributions of this paper are as follows. We first formulate the optimal channel assignment and power allocation problem. Then, we present an optimal centralized algorithm for this problem based on bipartite matching. For a single-hop CRN, we develop a CSMA-based MAC protocol, called AW-MAC, which realizes the centralized algorithm in a distributed manner. The centralized algorithm requires global information, which is hard to obtain in a multi-hop environment. Accordingly, for a multi-hop CRN, we present an efficient distributed channel assignment that relies only on information provided by the two communicating users. Our distributed scheme improves CRN throughput performance through cooperative assignment among neighboring CR users. Specifically, a CR user that intends to transmit has to account for potential future transmissions in its neighborhood. Based on this distributed scheme, we then develop a novel CSMA-based MAC protocol (WFC-MAC). Our protocols do not require interaction with PR networks (PRNs), and can be adapted to existing multi-channel systems with little extra processing overhead.

To evaluate the performance of our protocols, we conduct simulations for a single-hop and a multi-hop CRN with mobile users. Simulation results show that our protocols significantly improve the network throughput over two previously proposed schemes (i.e., BMC-MAC [START_REF] Jain | A multichannel CSMA MAC protocol with receiver-based channel selection for multihop wireless networks[END_REF][START_REF] Bany Salameh | MAC protocol for opportunistic cognitive radio networks with soft guarantees[END_REF] and DDMAC [START_REF] Bany Salameh | Cooperative adaptive spectrum sharing in cognitive radio networks[END_REF]). The results also indicate that our protocols preserve (even slightly improve) throughput fairness. For single-hop scenarios, we show that AW-MAC achieves the best throughput (up to 50% improvement over BMC-MAC scheme) at no additional cost in energy consumption. In multi-hop scenarios, WFC-MAC achieves the best throughput at the cost of energy consumption.

The rest of the paper is organized as follows. In Section 2, we introduce our system model, state our assumptions, and formulate the optimal channel assignment/power control problem. Section 3 introduces the centralized channel assignment algorithm. Section 3.2 describes the proposed AW-MAC protocol. In Section 4, we introduce the distributed channel assignment algorithm and the proposed WFC-MAC protocol. In Section 5, we analysis the throughput of our proposed protocols. Section 6 presents our simulation results. Our concluding remarks are presented in Section 7.

Problem Formulation and Design Constraints

Network Model

We consider a decentralized opportunistic CRN that geographically coexists with M different PRNs. The PRNs are licensed to operate on non-overlapping frequency bands, each of Fourier bandwidth W . For k = 1, . . . , M , the carrier frequency associated with the kth PRN is f k (in Hz). Let M denote the set of all non-overlapping channels in all PRNs (i.e., M = |M|).

CR users continuously identify potential spectrum holes and exploit them for their transmissions. They employ power control to avoid harmful interference with PR receptions. Specifically, CR users adopt the following transmission power strategy: for band i, i = 1, . . . M , the maximum CR transmission power is 0 if any PR user operates on band i, or limited to P (i) max if no PR signal is detected (i.e., the transmission power ≤ P

(i) max ). P (i)
max is the smaller of the FCC regulatory maximum transmission power over band i and the maximum power supported by the CR's battery (P CR ). Note that identifying the list of idle channels that is potentially available for CR transmissions at a given time and in a given geographical location is a challenging problem. To deal with this challenge, the FCC recently adopted three principal methods that can be used to determine the list of idle channels that is potentially available for CR transmissions at a given time and in a given geographical location [11]. The first method requires determining the location of a CR user and then accessing a database of licensed services (internal or external database) to identify busy/idle PR channels. The second method is to integrate spectrum sensing capabilities in the CR device. The third method is to periodically (or on-demand) transmit control information from a professionally installed fixed broadcast CR station. This control information contains the list of idle channels. Under this method, a CR transmitter can only transmit when it receives a control information that positively identifies idle PR channels. According to the FCC, this control information can also be transmitted by external entities, such as PR base stations (e.g., broadcast TV and radio stations). For our purposes, we assume that the control signal method is in place for determining the list of idle channels.

Feasibility Constraints

For a CR transmission j, transmitter and receiver need to cooperatively select an appropriate channel and transmission power while meeting the following constraints:

1. Exclusive channel occupancy policy: The selected channel cannot be assigned to more than one CR transmission in the same neighborhood (inline with the CSMA/CA mechanism). 2. One transceiver per CR user : Each CR user can transmit or receive on one channel only. The operation is half-duplex, i.e., a CR user cannot transmit and receive at the same time.

3. Maximum transmission power : For a CR transmission j and idle channel i, the transmission power P (i) j is limited to

P (i)
max . If channel i is occupied by a PR user, P (i) j = 0. 4. Rate demand : Each CR transmission j requires a given data rate R j . If none of the idle channels can support R j , the CR transmission j will be blocked.

Problem Formulation

At a given time t, let N (t) and M Idle (t) ⊆ M respectively denote the set of all CR transmission requests and the set of all |M Idle (t)| = M Idle (t) idle channels in a given neighborhood. Let N (t) = |N (t)|. It has been shown that neighboring CR users in a given locality typically share a similar view of spectrum opportunities (i.e., the set of common idle channels) [START_REF] Zhao | Distributed coordination in dynamic spectrum allocation networks[END_REF][START_REF] Bany Salameh | Channel Access Protocols for Multihop Opportunistic Networks: Challenges and Recent Developments[END_REF]. Given the rate demands (R j , ∀j ∈ N (t)) and the set of idle channels M Idle (t), our goal is to compute a feasible channel assignment that assigns channels and transmission powers to CR requests such that the number of feasible concurrent CR transmissions is maximized subject to the previously mentioned constraints. If multiple solutions exist for this optimization problem, we seek the one that requires the least amount of energy. Because we focus on computing a feasible channel assignment at a given time t, in what follows, we drop the time subscript (t) for notational convenience. Let α (i) j be a binary variable that is defined as follows:

α (i) j = 1, if channel i is assigned to transmission j 0, otherwise. (1)
The resource assignment problem is stated as follows:

maximize α (i) j ,P (i) j i∈M Idle j∈N α (i) j 1[r (i) j ≥ R j ] - 1 P tot i∈M Idle j∈N α (i) j P (i) j Subject to j∈N α (i) j ≤ 1, ∀i ∈ M Idle i∈M Idle α (i) j ≤ 1, ∀j ∈ N 0 ≤ P (i) j ≤ P (i) max , ∀i ∈ M Idle and ∀j ∈ N (2)
where 1[.] is the indicator function, r

(i) j = f (P (i)
j ) is the data rate for link j on channel i, f (.) is monotonically nondecreasing rate-power function (It can be Shannons capacity or any other power-rate function), and

P tot = i∈M P (i) max .
The second term in the objective function ensures that if multiple solutions exist for the optimization problem, the one with the least amount of total transmission power will be selected. Note that the first two constraints in [START_REF] Bany Salameh | Channel Access Protocols for Multihop Opportunistic Networks: Challenges and Recent Developments[END_REF] ensure that at most one channel can be assigned per transmission and a channel cannot be assigned to more than one transmission.

The third constraint ensures that

P (i) j P (i) max ≤ 1.
Given the above three constraints and noting that M Idle ⊆ M, the second term of the objective function is always < 1 (i.e., 1

Ptot i∈M Idle j∈N α (i) j P (i) j < 1)
. So, for any two feasible assignment Ω 1 with N 1 of admitted CR transmissions and Ω 2 with N 2 < N 1 of admitted CR transmissions, the above formulation will also selects Ω 1 over Ω 2 , irrespective of the total transmission power.

The optimization problem in (2) is a mixed integer non-linear program (MINLP). Due to integrality constraints, one expects such a problem to be NP-hard. However, we show that this MINLP is not NP-hard and may be solved optimally in polynomial time. Specifically, we show that this problem is the same as assigning channels to independent (distinct) links such that the number of feasible CR transmissions is maximized while using the minimum total transmission power. In Section 3, we propose an algorithm that transforms this optimization problem into the well-known maximum weighted perfect bipartite matching problem, which has a polynomial-time solution [START_REF] Sedgewick | Algorithms in C, Part 5: Graph Algorithms[END_REF].

Remark: For multi-transceiver case, the joint channel/power assignment problem is known to be NP-hard [START_REF] Bany Salameh | Cooperative adaptive spectrum sharing in cognitive radio networks[END_REF][START_REF] Behzad | Multiple access protocol for power-controlled wireless access nets[END_REF].

Optimal Channel Assignment

In this section, we first present a centralized algorithm for the channel assignment problem based on bipartite matching. The objective of this algorithm is to maximize the total number of feasible concurrent CR transmissions by means of power management. Note that centralized algorithms are easy to implement in single-hop networks where all users are within radio range of each other. Based on this centralized algorithm, we develop a CSMA-based MAC protocol that can be executed in a distributed manner.

Proposed Algorithm

In our context, a centralized algorithm implies that the instantaneous SINR values, location information, and rate demand are known to the decision-making entity that assigns channels and transmission powers. For a finite number of available channels and given rate demands, a CR user can compute the minimum required power over each channel. Using this fact and noting that the graph connecting the set of CR transmission requests and the set of available channels is a bipartite graph1 , our optimization problem can be transformed into a bipartite perfect matching problem. The maximum matching of this bipartite graph problem is the set containing the maximum number of feasible CR transmissions that can proceed concurrently. If there are multiple feasible channel assignments with maximum matching, the one requiring the smallest total transmission power will be selected. In the following, we develop an algorithm that transforms our optimization problem into a bipartite perfect matching problem. Formally, the algorithm proceeds in 3 steps:

Step 1. Compute the minimum required powers: For every CR transmission request j ∈ N and every idle channel i ∈ M Idle , the algorithm computes the minimum required transmission power P (i) j,req that can support the rate demand R j , i.e., P (i) j,req = f -1 (R j ). Then, the algorithm identifies prohibited (infeasible) channel/transmission combination (i, j) whose P (i) j,req does not satisfy the maximum transmission power constraint (i.e., P

(i) j,req > P (i) max ).
Step 2. Formulate the perfect bipartite matching problem: The algorithm creates M Idle nodes, each corresponding to one of the idle channels. Let these nodes constitute the channel set C. The algorithm also creates N nodes to represent the CR transmission requests. Let these nodes constitute the request set R.

If N > M Idle , the algorithm creates N -M Idle additional nodes C D = {M Idle + 1, . . . M Idle + N } to represent dummy channels and updates C as C = C C D . On the other hand, if N < M Idle , the algorithm creates M Idle -N additional nodes R D = {N + 1, . . . M Idle + N } to represent dummy requests and updates R as R = R R D .
Then, the algorithm connects the nodes in C to the nodes in R. Any (i, j) assignment that contains a dummy node is also a prohibited assignment. Let w (i) j denote the arc weight of link (i,j) on the bipartite graph. For all prohibited assignments, the algorithm sets w (i) j to a very large number Γ P CR .. Formally,

w (i) j = P (i) j,req , if P (i) j,req ≤ P (i) max , j ∈ R and i ∈ C w (i) j = Γ, if P (i) j,req > P (i) max , j ∈ R and i ∈ C. (3)
The above bipartite graph construction transforms the assignment problem into a perfect bipartite matching (because the number of CR transmissions is equal to the number of channels, and every node in the request set is connected to every node in the channel set). Now, the algorithm seeks a one-to-one assignment for the max{M Idle , N }×max{M Idle , N } bipartite graph constructed in Step 2, with the weights defined in (3), so as the channel utilization is maximized while selecting the minimum transmission powers. Particularly, the mathematical formulation of the assignment problem corresponds to a weighted perfect bipartite matching problem. Hence, the global optimal channel assignment solution (i.e., α (i) j ) can be found using the Hungarian algorithm, which has a polynomial-time complexity (i.e., O( √ KK), where K = max{N, M Idle } [START_REF] Sedgewick | Algorithms in C, Part 5: Graph Algorithms[END_REF]) and codes are readily available for its implementation [START_REF] Dendeit | Max-Min matching problems with multiple assignments[END_REF].

Step 3. Find the optimal resource allocation: The algorithm removes all prohibited assignments in the optimal channel solution by setting them to 0, and modifies α (i) j as follows:

α * (i) j = 1, if α (i) j = 1 and w (i) j < Γ , j ∈ R and i ∈ C α * (i) j = 0, if α (i) j = 1 and w (i) j = Γ , j ∈ R and i ∈ C. (4)
Using the revised optimal assignment {α * (i) j }, the algorithm computes Z = i∈C j∈R α * (i) j . Depending on Z, there are two possibilities:

-If Z = 0, there is no feasible channel assignment.

-If Z > 0, there is a feasible channel assignment. In this case, Z represents the maximum number of possible concurrent transmissions.

Channel Access Protocol for Single-hop CRNs

Based on the channel assignment algorithm presented in Section 3.1, we now propose a distributed multi-channel MAC protocol for single-hop ad hoc CRNs with a single half-duplex radio per node. Before describing our protocol in detail, we first state our main assumptions.

Assumptions: For each frequency channel, we assume that its gain is stationary for the duration of a few control packets and one data packet. This assumption holds for typical mobility patterns and transmission rates [START_REF] Muqattash | POWMAC: A single-channel power control protocol for throughput enhancement in wireless ad hoc networks[END_REF]. We also assume symmetric gains between two users, which is a common assumption in RTS/CTS-based protocols, including the IEEE 802.11 scheme. Our protocols assume the availability of a prespecified common control channel.Such a channel is not necessarily dedicated to the CRN. It may, for example, be one of the unlicensed ISM bands. Note that the existence of a common control channel is a characteristic of many MAC protocols proposed for CRNs (e.g., [START_REF] Bany Salameh | Cooperative adaptive spectrum sharing in cognitive radio networks[END_REF][START_REF] Yuan | Knows: Kognitive networking over white spaces[END_REF][START_REF] Bany Salameh | MAC protocol for opportunistic cognitive radio networks with soft guarantees[END_REF]).

Operational Details: To execute the centralized algorithm presented in the previous section in a distributed manner, we require the instantaneous SINR information and rate demands of all contending CR users in a given locality to be known to all CR users in that locality before assigning channels and transmission powers. In a single-hop network, this issue can be handled during the "admission phase" by introducing a contention period known as the access window (AW). The AW consists of M Idle fixed-duration access slots (AS). A series of control packet exchanges take place during these slots, after which several data transmissions can commence concurrently. We note here that the use of an AW for contention was originally proposed in the MACA-P protocol [START_REF] Acharya | MACA-P : a MAC for concurrent transmissions in multi-hop wireless networks[END_REF] and was later integrated in the design of POWMAC [START_REF] Muqattash | POWMAC: A single-channel power control protocol for throughput enhancement in wireless ad hoc networks[END_REF]. However, in both protocols the objective was not to address spectrum sharing (channel assignment), but rather to prevent collisions between control and data packets (in MACA-P) and to address single-channel transmission power control (in POWMAC). During the AW, communicating CR users announce their instantaneous SINR information. A CR user that has packets to transmit and that is not aware of any already established AW in its neighborhood can asynchronously initiate an AW. Each AS consists of the sum of an RTS duration, a CTS duration, and a maximum backoff interval (explained below), and two fixed short interframe spacing (SIFS) periods2 . Control packets are sent at the maximum (known) power P ctrl . This P ctrl is constrained by the maximum permissible transmission power imposed on the control channel. Upon receiving an RTS packet from a CR user, say A, that is initiating an AW, other CR users in the network synchronize their time reference with A's AW. Suppose that a CR user C overhears A's RTS, and has a data packet to send. C contends for the control channel in the next access slot of A's AW as follows. It first backs off for a random duration of time (T ) that is uniformly distributed in the interval [0, T max ]; T max is a system-wide backoff counter. After this waiting time and if no carrier is sensed, user C sends its RTS packet in the current AS. Note that T max is in the order of a few microseconds whereas a time slot is in milliseconds, so the backoff mainly serves to prevent synchronized RTS attempts. For illustration purposes, Figure 1 shows a time diagram of the channel access process, assuming fixed data-packet sizes and equal rate demands. T ctrl and T data in the figure denote the durations (in seconds) of one RTS/CTS packet exchange and one data plus ACK packets transmissions, respectively.

After all the control packets have been exchanged, the channel assignment and power management algorithm of Section 3 is executed at every communicating node.

Remarks and Design Variants

Granularity of Channel Assignment: Depending on channel availability due to PR dynamics, the proposed channel assignment can be performed at the granularity of a packet or a link. In the latter case, the assignment applies to all packets of the current connection between the two end points of a link.

Fairness Properties of AW-MAC: According to AW-MAC, CR users contend over the control channel using a variant of the CSMA/CA mechanism. This gives all CR users the same probability of accessing channels, irrespective of their rate demands. Thus, our AW-MAC protocol preserves fairness among CR users. In our simulations (Section 6), we compare the fairness properties of AW-MAC to that of typical multi-channel CRN CSMA-based protocols. The results show that AW-MAC preserves (slightly improves) the network fairness.

Channel Assignment with a Multi-level Frequency-dependent Power Constraint: The problem of identifying spectrum holes and selecting appropriate channels/powers is overcomplicated by the presumingly non-cooperative nature of PRNs, which usually do not provide feedback (e.g., interference margins) to CR users. To address this problem, a multi-level time-varying frequency-dependent power mask (P mask = {P mask }) on the CR transmissions is often adopted (e.g., [START_REF] Bany Salameh | Cooperative adaptive spectrum sharing in cognitive radio networks[END_REF]). Enforcing such a power mask allows for spectrum sharing between neighboring CR and PR users. According to this approach, CR users can exploit both idle as well as partially-utilized bands, potentially leading to better spectrum utilization. However, the determination of an appropriate multi-level power mask is still an open issue, which has been recently investigated under certain simplifying assumptions (e.g., [START_REF] Bany Salameh | MAC protocol for opportunistic cognitive radio networks with soft guarantees[END_REF][START_REF] Bany Salameh | Channel Access Protocols for Multihop Opportunistic Networks: Challenges and Recent Developments[END_REF]). Although our proposed algorithm assumes a binary-level power constraint on CR transmissions, the algorithm is still valid for the case of a multi-level frequency-dependent power mask by setting the maximum CR transmission power over channel i to

P (i) max = min{P (i) mask , P CR }, ∀i ∈ M.
AW-MAC with Two Transceivers: Another design possibility that can achieve improvement in the CRN throughput is to use two half-duplex transceivers per CR user. One transceiver would be tuned to the control channel, while the other could be tuned to any data channel in M Idle . Because there is no interference between data and control transmissions (the two are separated in frequency), the reservations of the subsequence AW can be conducted while current data transmissions are taking place (i.e., mimicing a full-duplex operation). This reduces the control overhead and improves the overall throughput at the cost of an additional transceiver. We refer to the channel access mechanism that uses AW assignment with one transceiver as AW-MAC, and the one that uses AW assignment with two transceivers as 2-radio AW-MAC. Figure 2 shows the basic operation of 2-radio AW-MAC. In Section 5, we study the potential throughput improvement of 2-radio AW-MAC over AW-MAC. RTS/CTS handshake in AW-MAC: It should be noted that the RTS/CTS handshake is essential in multi-channel systems (e.g., CRNs). Besides mitigating the hidden-terminal problems, there are two other main objectives for the use of RTS/CTS: (1) conducting and announcing the channel assignment, and (2) prompting both the transmitter and the receiver to tune to the agreed on channels before transmission commences. Simulation studies have shown that using RTS/CTS packets for data packets larger than 250 bytes is beneficial [START_REF] Crow | IEEE 802.11 wireless local area networks[END_REF] 3 . It is also worth mentioning that our AW-MAC protocol is based on passive learning. This is because in AW-MAC, CR users are within the transmission range of each other and always listen to the control channel in order to overhear control-packet exchanges, including those not destined to them. CR users use the control information to perform the channel assignment. Thus, AW-MAC does not introduce any additional control message overhead beyond the needed two-way handshake for every transmitted data packet.

Distributed Channel Assignment for Multi-hop CRNs

In this section, we present a distributed channel assignment scheme for a multi-hop CRN. It attempts to improve spectrum utilization in a purely distributed manner while relying only on information provided by the two communicating nodes. We first identify the key challenges involved in realizing the centralized algorithm in a distributed manner. Then, we describe our distributed scheme in detail.

Challenges

To execute our centralized algorithm in a multi-hop environment, the algorithm must run in a distributed manner at each CR device in a given locality (i.e., contention region). This implies that each CR user that belongs to a contention region must exchange instantaneous SINR information with other neighboring CR users in that region before selecting channels and powers. This incurs high control overhead and delay. Moreover, in a multi-hop environment, CR users may belong to multiple contention regions that differ in their views of the spectrum opportunity. To overcome such challenges, we develop a heuristic channel assignment scheme that provides a suboptimal solution with low complexity and that achieves good spectrum utilization.

Channel Assignment

The main consideration in our distributed scheme is to enable cooperation among neighboring CR users. A CR user that intends to transmit has to account for potential future transmissions in its neighborhood. It does that by assigning to its transmission the worst feasible channel, i.e., the least-capacity available channel that can support the required rate demand. We refer to this approach as the worst feasible channel (WFC) scheme. Note that a user determines the worst feasible channel for its transmission using only local information. WFC scheme preserves better channels for potential future CR transmissions. Even though WFC requires a pair of CR users to communicate on a channel that may not be optimal from one user's perspective, it allows more CR transmissions to take place concurrently, especially under moderate to high traffic loads. Compared to previously proposed channel assignment schemes (evaluated in Section 6), our approach avoids unnecessary blocking of CR transmissions, and has a great potential to improve network throughput by means of cooperative channel assignment.

Channel Access Protocol

Protocol Overview: Based on the WFC algorithm, we propose a distributed multi-channel MAC protocol for multi-hop ad hoc CRNs with a single half-duplex radio per node. The proposed protocol is an extension of the single channel RTS-CTS-DATA-ACK handshaking scheme used in the 802.11 standard. It differs from previous designs in that it exploits the "dual-receive single-transmit" capability of radios (i.e., each radio is capable of receiving over two channels simultaneously, but can transmit over one channel at a time). The operation is half-duplex, i.e., while transmitting, the radio cannot receive/listen, even over other channels. It can be implemented using one transceiver with slight upgrade in the receive chains of the circuitry. This capability is readily available in some recent radios. For example, QUALCOMM's RFR6500 radio [START_REF]Qualcomm Announces Sampling of the Industry's First Single-Chip Receive Diversity Device for Increased CDMA2000 Network Capacity[END_REF] supports "simultaneous hybrid dual-receive operation, which allows for 1X paging signal monitoring during a 1xEV-DO connection, while monitoring other frequency bands for hand-off". Another example is Kenwood's TH-D7A Dual-Band Handheld Transceiver [START_REF] Kenwood | 7A Dual-Band Handheld Transceiver[END_REF], which supports simultaneous reception over both data and voice channels using a single antenna. Though a simple enhancement of the transceiver circuitry, the dual-receive capability makes the MAC design much easier. In particular, if we assume a common (or coordinated) control channel, a CR user that is not transmitting any data can tune one of its two receive branches to the control channel while receiving data over the other receive branch. This way, the multi-channel hidden-terminal problem can be alleviated.

Operational Details: To facilitate multi-channel contention and reduce the likelihood of CR collisions, each CR user, say A, maintains a free-channel list (FCL) and a busy-node list (BNL). The FCL(A) represents idle PR channels that are not occupied by other CR users within the A's one-hop communication range. BNL(A) consists of the IDs of CR users that are currently busy transmitting/receiving data packets in A's neighborhood. The FCL(A) and BNL(A) are continuously updated according to the channel access dynamics and overheard control packets. The proposed protocol follows similar interframe spacings and collision avoidance strategies of the 802.11 scheme (implemented here over the control channel) by using physical carrier sensing and backoff before initiating control-packet exchanges. Upon accessing the control channel, communicating CR users perform a three-way handshake, during which they exchange control information, conduct the channel assignment, and announce the outcome of this channel assignment to their neighbors.

The details of the channel access mechanism are now described. Suppose that CR user A has data to transmit to CR user B at a rate demand R A . If A does not sense a carrier over the control channel for a randomly selected backoff period, it proceeds as follows:

-If FCL(A) is empty or B is busy (based on BNL(A)), A backs off and attempts to access the control channel later.

Otherwise, A sends an RTS message at power P ctrl . The RTS packet includes FCL(A) and R A . -A's neighbors other than B, that can correctly decode the RTS will stay silent until either they receive another control packet from A, denoted by FCTS (explained below), or until the expected time for the FCTS packet expires. -Upon receiving the RTS packet, B determines the common channel list that is available for A → B transmission, denoted by CCL(A, B). Then, B proceeds with the channel assignment process, whose purpose is to determine whether or not there exists a feasible channel assignment that can support R A . -Depending on the outcome of the channel assignment process, B decides whether or not A can transmit. If not (i.e., non of the channels in CCL(A, B) can support R A ), then B does not respond to A, prompting A to back off, with an increased backoff range that is similar to 802.11, and retransmit later. Otherwise, B sends a CTS message to A that contains the assigned channel, the transmit power, and the duration (T pkt (A)) needed to reserve the assigned channel. The CTS implicitly instructs B's CR neighbors to refrain from transmitting over the assigned channel for the duration T pkt (A). -Once A receives the CTS, it replies back with a "Feasible-Channel-to-Send" (FCTS) message, informing its neighbors of the assigned channel and T pkt (A). Such a three-way handshake is typically needed in multi-channel CSMA/CA protocols designed for multi-hop networks (e.g., [START_REF] Jain | A multichannel CSMA MAC protocol with receiver-based channel selection for multihop wireless networks[END_REF][START_REF] Bany Salameh | Cooperative adaptive spectrum sharing in cognitive radio networks[END_REF][START_REF] Bany Salameh | MAC protocol for opportunistic cognitive radio networks with soft guarantees[END_REF]). For single-hop networks, where all users can hear each other, there is no need for the FCTS packet. Likewise, in single-channel multi-hop networks, the FCTS packet is also not needed.

-After completing the RTS/CTS/FCTS exchange, the transmission A → B proceeds. Once completed, B sends back an ACK packet to A over the assigned data channel.

When used with the WFC assignment, the above protocol is referred to as WFC-MAC. Note that, while receiving a data packet over a given data channel, a CR user still listens to other control packet exchanges taking place over the control channel, and can update its FCL and BNL accordingly. However, a CR user that is transmitting a data packet will not be able to listen to the control channel, so its FCL and BNL may become outdated. We refer to this problem as transmitter deafness, which is primarily caused by the half-duplex nature of the radios. To remedy this problem, when the receiver sends its ACK, it includes in this ACK any changes in the FCL and BNL that may have occurred during the transmission of the data packet. The transmitter uses this information to update its own tables.

Because there is no interference between data and control packets, a CR user that hears the RTS (CTS) packet defers its transmission only until the end of the control packet handshaking. This allows for more parallel transmissions to take place in the same vicinity.

Throughput Analysis

In this section, we use simplified analysis to evaluate the maximum achievable throughput of various channel access schemes in single-hop topologies. We assume that a CR user transmits data in the form of fixed-size packets at a fixed transmission rate. Recall that T ctrl denotes the transmission duration of one RTS plus one CTS packets, and T data denotes the duration for data plus ACK transmissions. Assume that T ctrl can be expressed in terms of T data as T ctrl = δT data . It is worth mentioning that according to the IEEE 802.11 specifications, T data is at least an order of magnitude larger than T ctrl (i.e., 0 < δ 1). As an example, consider data-and control-packet sizes of 4-KB and 120 bits, respectively [START_REF]The Cisco Aironet 350 Series of wireless LAN[END_REF]. Also consider a transmission rate of 5Mbps. Then, δ ≈ 0.0073. We now provide expressions for the maximum achievable throughput under the various schemes assuming the availability of M Idle channels and a per-packet channel assignment. The maximum achievable throughput is defined as the maximum number of concurrent feasible CR transmissions that can be supported in a

T data + M Idle T ctrl = (1 + M Idle δ)T data duration.
For the single-transceiver AW-MAC, according to Figure 1, the maximum number of data packets that can be potentially transmitted in a T data + M Idle T ctrl duration is M Idle . Under 2-radio AW-MAC, at steady state, the maximum number of data packets that can be potentially transmitted in the same duration is 2). Under both WFC-MAC and BMC-MAC (similar to WFC-MAC but uses the BMC channel assignment), for a given channel i, Figure 3 shows that an RTS/CTS exchange can immediately follow the transmission of the previous data packet over that channel. Thus, the maximum achievable throughput in the

M Idle + M Idle i=1 M Idle T ctrl T data = M Idle + M 2 Idle δ = M Idle (1 + M Idle δ) (see Figure
T data + M Idle T ctrl duration is M Idle + M Idle -1 i=1 (M Idle -i -1) T ctrl
T data . With some manipulations, this quantity can be written as

M Idle + δ( M 2 Idle 2 -3 2 M Idle + 1
). Computing the maximum achievable throughput in this way is rather optimistic since we are assuming that for 2-radio AW-MAC/AW-MAC, all AW slots result in successful RTS/CTS exchanges, and that for the BMC-MAC/WFC-MAC and a given data channel, an RTS/CTS exchange follows immediately the transmission of the previous data packet over that channel.

Figure 4 shows the maximum achievable throughput as a function of M Idle for two data-packet sizes and various channel access schemes. For practical data-and control-packet sizes [START_REF]The Cisco Aironet 350 Series of wireless LAN[END_REF], where δ 1, the figures reveal that various channel access schemes achieve comparable throughput performance. More importantly, the use of two half-duplex transceivers per CR user provides a minor improvement in the system throughput over a single-transceiver design. The figures also demonstrate that the throughput gain due to two transceivers is larger at smaller data-packet sizes (i.e., larger δ) and larger M Idle . This is because a larger δ (or M Idle ) means larger a AW duration, which results in more overhead for the single-transceiver solution.

Performance Evaluation

We now evaluate the performance of the proposed protocols via simulations. Our proposed protocols (AW-MAC and WFC-MAC) are compared with two CRN MAC protocols: BMC-MAC [START_REF] Bany Salameh | MAC protocol for opportunistic cognitive radio networks with soft guarantees[END_REF] and DDMAC [START_REF] Bany Salameh | Cooperative adaptive spectrum sharing in cognitive radio networks[END_REF]. As mentioned before, BMC-MAC selects the best available channel for data transmission. DDMAC is a CSMA-based spectrum-sharing protocol for CRNs. It attempts to maximize the CRN throughput through a probabilistic channel assignment algorithm that exploits the dependence between the signal's attenuation model and the transmission distance while considering current traffic and interference conditions. For a fair comparison, in BMC-MAC, WFC-MAC, and DDMAC, CR users employ the same channel access mechanism described in Section 4.3. They differ in the channel assignment approach. The maximum achievable throughput under DDMAC channel access is the same as the one obtained in Section 5 for WFC-MAC/BMC-MAC and is comparable to the one for AW-MAC (see Figure 4). Note that, in all protocols, if there is no feasible channel assignment that can support the rate demand, no channel will be assigned, prompting the transmitter to back off. It is worth mentioning that DDMAC involves more processing overhead, as it requires distance and traffic estimation. In our evaluation, we first study the network performance in a single-hop CRN, where all users can hear each other. Then, we study it in a multi-hop mobile CRN. Our results are based on simulation experiments conducted using CSIM, a C-based, process-oriented, discrete-event simulation package [22]. Fig. 5. CRN performance in single-hop scenarios.

Simulation Setup

We consider four PRNs and one CRN that coexist in a 100 meter × 100 meter field. Users in each PRN are uniformly distributed. The PRNs operate in the 600 MHz, 900 MHz, 2.4 GHz, and 5.7 GHz bands, respectively. Each PRN consists of three 2.5-MHz-wide channels, resulting in a maximum of 12 channels for opportunistic transmissions. We divide the time into slots, each of length 6.6 ms. A time slot corresponds to the transmission of one data packet of size 4-KB at a transmission rate of 5 Mbps. Each user in the kth PRN acts as an ON/OFF source, where it is ON while transmitting and OFF otherwise. The source is further characterized by the distribution of its ON and OFF periods, which are both taken to be exponential. We set the average ON and OFF periods for the four PRNs to be the duration of 10 and 190 time slots, respectively. The number of PR links in each PRN is 20. Each active link in the kth PRN transmits over one of the 3 channels in its own band. Thus, the available spectrum opportunity in each PR band is 66.7%. For the CRN, we consider 200 mobile users. The random waypoint model is used for mobility, with the speed of a CR user uniformly distributed between 0 and 2 meters/sec. For each generated packet, the destination node is selected randomly. Each CR user generates fixed-size (2-KB) data packets according to a Poisson process of rate λ (in packet/time slot). Each user requires a transmission rate of 5 Mbps. We set the CRN SINR threshold to 5 dB and the thermal noise power density to P (i) th = 10 -21 Watt/Hz for all channels. We set the maximum transmission power to P

(1)

max = P (2) max = . . . = P (12)
max = 50 mW and the control-packet size to 120 bits. The data rate of a CR transmission over a given channel is calculated according to Shannon's formula 4 . The reported results are averaged over 100 runs. Our performance metrics include: (1) the network throughput, (2) the CR blocking rate, (3) the average energy consumption for successfully transmitting one data packet (E p ), and (4) the fairness index. The CR blocking rate is defined as the percentage of CR requests that are blocked due to the unavailability of a feasible channel. We use Jain's fairness index [START_REF] Jain | The Art of Computer System Performance Analysis[END_REF] to quantify the fairness of a scheme according to the throughput of all the CR users in the network.

Single-hop Network

We first study the throughput performance. Figures 5(a) and (b) show that 2-radio AW-MAC provides only minor improvement in the network throughput over the single transceiver AW-MAC (this result is inline with the analysis in Section 5). Because both 2-radio AW-MAC and AW-MAC use the same channel assignment algorithm and provide comparable throughput performance, in the following, we focus on the performance of AW-MAC and compare it with the performance of the other protocols. Specifically, Figures 5(a) and (b) show that under moderate and high traffic loads, AW-MAC significantly outperforms the other protocols. At steady state, AW-MAC reduces the CR blocking rate and improves the overall one-hop throughput by up to 50% compared to BMC-MAC, 18% compared to DDMAC, and 12% compared to WFC-MAC. This improvement is mostly attributed to the increase in the number of simultaneous CR transmissions. WFC-MAC outperforms both BMC-MAC and DDMAC. This is because WFC-MAC attempts to serve a given CR transmission first using the worst feasible channel and preserves better channels for potential future transmissions. Under light loads, all protocols achieve comparable throughput performance. In Figure 5(c), we study the impact of the channel assignment strategy on E p . It is clear that WFC-MAC and DDMAC perform the worst in terms of energy consumption. At the same time, the figure reveals that 2-radio AW-MAC, AW-MAC, and BMC-MAC have comparable performance with respect to E p . Thus, the throughput advantage of AW-MAC does not come at the expense of additional energy consumption.

Figure 5(d) shows that all schemes achieve comparable fairness. This can be attributed to the fact that in all of these schemes CR users contend over the control channel using a variant of the CSMA/CA mechanism. Finally, Figure 5(e) depicts the channel usage, defined as the fraction of time in which a specific channel is used for CR transmissions. For WFC-MAC and DDMAC, channel usage is roughly evenly distributed among all channels, irrespective of the traffic load. For AW-MAC and BMC-MAC, under low and moderate traffic loads, channels with lower carrier frequencies are favored for CR transmissions (lower attenuation). On the other hand, under high traffic load, there are no significant differences in channel usage among all channels. In order to study the performance in a multi-hop environment, we use the same simulation setup described in Section 6.1, but with the following changes:

Multi-hop Network

-A 500 meter × 500 meter field is considered for the 200 mobile CR users.

-The maximum transmission power is set to P -Each CR user generates 2-KB data packets according to a Poisson process of rate λ. For each generated packet, the destination node is randomly selected to be any node in the network. We use a min-hop routing policy, but we ignore the routing overhead. For all schemes (BMC-MAC, WFC-MAC, and DDMAC), the next-hop candidates are nodes that are within the transmission range of the transmitter.

The purpose behind these changes in the setup is to give rise to hidden terminals. Our simulations take into account the effect of the hidden-terminal problem due to imperfect control and inaccurate ACL at both the receiver and transmitter by considering the interference from active neighboring CR transmissions that use common channels (if any).

As shown in Figures 6(a) and (b), WFC-MAC achieves lower CR blocking rate and higher end-to-end network throughput than the other two protocols under moderate and high traffic loads. On the other hand, under low traffic load, all protocols achieve comparable throughput performance. Figure 6(c) shows that BMC-MAC outperforms WFC-MAC and DDMAC in terms of E p under different traffic loads. Similar fairness and channel usage properties to the single-hop scenarios are also observed here.

Note that no single strategy is always best in all traffic regimes. Under light traffic, BMC-MAC provides the same throughput performance as WFC-MAC and DDMAC, but outperforms them in terms of E p . However, under moderate and high traffic loads, WFC-MAC performs better in terms of throughput at the cost of E p .

Conclusion

In this paper, we investigated the design of cooperative dynamic channel assignment for single-transceiver CR devices that employ adaptive power management. Our solutions attempt to maximize the network throughput as a primary objective, followed by minimizing energy consumption as a secondary objective. We first presented centralized and distributed channel assignment algorithms. For single-hop CRNs, we developed a CSMA-based MAC protocol with access window (AW) for exchanging control messages. Our AW-MAC realizes the optimal centralized channel assignment in a distributed manner. Based on our heuristic distributed assignment, we also developed a distributed, asynchronous MAC protocol (WFC-MAC) for multi-hop CRNs. We studied the performance of our protocols and contrasted them with two previously proposed MAC protocols (i.e., BMC-MAC and DDMAC). We showed that for single-hop CRNs, AW-MAC performs the best in terms of throughput and energy consumption under various traffic conditions. Under moderate-to-high traffic loads, AW-MAC achieves about 50% increase in throughput over BMC-MAC at no additional cost in energy. It achieves about 18% throughput improvement over DDMAC, with even less energy consumption and processing overhead. For multi-hop scenarios, our results show that WFC-MAC is the best strategy in terms of throughput at the cost of energy consumption under different traffic loads.

Fig. 1 .

 1 Fig. 1. Basic operation of AW-MAC.

Fig. 2 .

 2 Fig. 2. Basic operation of 2-radio AW-MAC (Note that M Idle (t o ) = M o and M Idle (t 1 ) = M 1 ).

Fig. 3 .

 3 Fig. 3. Basic operation of the distributed spectrum access scheme.

Fig. 4 .

 4 Fig.[START_REF] Sabharwal | Opportunistic spectral usage: Bounds and a multi-band CSMA/CA protocol[END_REF]. Maximum achievable throughput (in packet/ (T data +M Idle T ctrl )) vs. total number of idle channels (control-packet size = 120 bits).

  Fairness index (2-radio AW-MAC depicted similar behavior as AW-MAC) CR channel usage (2-radio AW-MAC depicted similar behavior as AW-MAC)

Fig. 6 .

 6 Fig.6. CRN performance in multi-hop scenarios.

A bipartite graph is a graph whose vertex set can be decomposed into two disjoint sets such that no two vertices in the same set are connected.

As defined in the IEEE 802.11b standard[START_REF] Bany Salameh | Channel Access Protocols for Multihop Opportunistic Networks: Challenges and Recent Developments[END_REF], a SIFS period consists of the processing delay for a received packet plus the turnaround time.

The RTS threshold depends on the number of users in the network[START_REF] Crow | IEEE 802.11 wireless local area networks[END_REF][START_REF] Bianchi | Performance analysis of the IEEE 802.11 distributed coordination function[END_REF]. It should be reduced for a large number of users.

Other rate-vs-power relationships, such as a staircase function, can be used for calculating the achievable data rates.

This research was supported in part by NSF (under grants CNS-1016943, CNS-0721935, CNS-0904681, IIP-0832238), Raytheon, and the Connection One center. Any opinions, findings, conclusions, or recommendations expressed in this paper are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.


Corentin Briat
email: cbriat@kth.se

Emre A Yavuz
email: emreya@kth.se

Gunnar Karlsson

Impact of queueing delay estimation error on equilibrium and its stability

Keywords: Congestion Control, FAST-TCP, Time-Delay Systems, fairness, stability

Delay-based transmission control protocols need to separate round-trip time (RTT) measurements into their constituting parts: the propagation and the queueing delays. We consider two means for this; the first is to take the propagation delay as the minimum observed RTT value, and the second is to measure the queueing delay at the routers and feed it back to the sources. We choose FAST-TCP as a representative delay-based transmission control protocol for analysis and study the impact of delay knowledge errors on its performance. We have shown that while the first method destroys fairness and the uniqueness of the equilibrium, the stability of the protocol can easily be obtained through tuning the protocol terms appropriately. Even though the second technique is shown to preserve fairness and uniqueness of the equilibrium point, we have presented that unavoidable oscillations can occur around the equilibrium point.

Introduction

Most recent developments for the internet have concerned the development of delay-based congestion control and its instantiation in the form of FAST-TCP [START_REF] Wei | FAST TCP: motivation, architecture, algorithms, performance[END_REF]. It is possible to get better performance in terms of shorter queues and lower losses, both resulting in lower end-to-end delay for a transfer, when control is based on a continuous state variable rather than the binary signal of a packet drop. We have in a previous work shown that knowledge of both queuing and propagation delays is necessary and sufficient to obtain stability, fairness, and efficiency in distributed congestion control, such as TCP [START_REF] Sandberg | On performance limitations of congestion control[END_REF]. In this paper, we study how these measures are obtained and the impact any imperfection could have on the control performance.

Motivation The motivation to study congestion control relates to its importance for network operation. Mission critical information systems, for instance supervisory control and data acquisition systems used for controlling the power grid, are increasingly relying on internet communication for both system status data and control commands. The trend to port such systems from proprietary low speed data networks to the internet is based on ready availability of higher capacity and low delay that improve system operation (such as smart grid); the cost to provide similar connection quality by proprietary networks might not be justifiable for competitive reasons. A network without congestion control may still be efficient given perfect error handling in the form of selective repeat ARQ or erasure coding [START_REF] Bonald | Is the "law of the jungle" sustainable for the internet?[END_REF] as shown in a recent work by Bonald et al. The proviso is that one of two possible conditions must be met: The first is that the capacities of access links are small with respect to the shared links, in which case the efficiency is high for drop-tail FIFO queues. The second is by using a fair-drop policy in routers for which the sharing will also be fair. Noting the increases in access links owing to commercial offering of 100 Mb/s and higher-rate DSL connections, and of fiber to homes that are increasingly being installed, we conclude that the fair-drop mechanism appears necessary before daring to dismantle congestion control. An additional disadvantage with unregulated elastic flows is that the sharing with inelastic flows is obliterated; while it is possible to share resources between the two types by qualitative differentiation of traffic controls (rate control for elastic flow and admission control of inelastic flows) [START_REF] Lundqvist | Edge-based differentiated services[END_REF]. Hence, we believe congestion control remains a vital function for sound internet operation for a foreseeable future.

Contributions This paper reports new analytical results on the performance of delay-based congestion control. We present how the estimation of queueing delay from samples of round-trip delay may cause unfairness among competing flows and instability if the protocol tuning parameters are not chosen accordingly. The alternative is to measure the queueing delay in routers and feed back those measures to all senders; hence ensuring fairness since all act on the same information. In such a case, the error at equilibrium will be the same for all users leading to a unique and fair equilibrium point. However, due to the quantization of the measurements, we have proved that the network will inevitably exhibit an oscillating behavior. Our analysis is based on time-delay systems theory and it involves large polynomials and complex transcendental equation analysis, which is typically unsolvable analytically except in very simple cases. Thus, we have considered only the single-user/single-buffer case to obtain the results for the stability analysis. It is however important to stress that our results may be scaled to a more general context, at least qualitatively, since observed issues that occur for the single-user/single-buffer topology, are expected to appear also for cases with complex topologies.

Outline of paper

The paper has the following outline. Section 2 covers the related work and in section 3 we give a brief overview of FAST-TCP. Section 4 presents the model for the delay based congestion avoidance protocols. In section 5 we analyze the impact of the queuing delay estimation error on equilibrium and its stability. Section 6 provides a similar analysis, yet considers the quantization error when measuring the queuing delay. We conclude the work in section 7.

Related Work

The congestion control algorithm implemented in TCP Reno [START_REF] Jacobson | Congestion avoidance and control[END_REF] has performed well and gone through several enhancements since then. It is however well-known that as bandwidth-delay product continues to grow, it will become a performance bottleneck itself. The poor performance of TCP Reno in such networks is due to slowness of linear increase by one packet per round-trip time, severeness of multiplicative decrease per loss event, the difficulty in maintaining large average congestion windows, which requires an extremely small equilibrium loss probability and using a binary congestion signal based on packet loss which causes oscillations.

Delay-based congestion control has been proposed in [START_REF] Jain | A delay-based approach for congestion avoidance in interconnected heterogeneous computer networks[END_REF][START_REF] Wang | Eliminating periodic packet losses in the 4.3-tahoe BSD TCP congestion control algorithm[END_REF][START_REF] Brakmo | TCP Vegas: End to end congestion avoidance on a global internet[END_REF] to overcome these difficulties. Control protocols established on delay-based congestion avoidance (DCA) algorithms are shown to achieve better performance than protocols established on congestion avoidance algorithms based on packet loss as network congestion indicator, with respect to network efficiency, stability and latency [START_REF] Wei | FAST TCP: motivation, architecture, algorithms, performance[END_REF][START_REF] Jain | A delay-based approach for congestion avoidance in interconnected heterogeneous computer networks[END_REF][START_REF] Brakmo | TCP Vegas: new techniques for congestion detection and avoidance[END_REF]. Queuing delay can be estimated more accurately compared to loss since packet losses are rare events, and information on queuing delay has finer resolution than what loss samples provide. In [START_REF] Sandberg | On performance limitations of congestion control[END_REF], several objectives (stability, fairness, efficiency) are considered and necessary conditions for a delay-based protocol to achieve these are provided. It is shown that knowledge of both the (aggregate) queuing delay and the constant propagation delay are necessary to ensure both fairness and efficiency.

DCA protocols react to shifts in measured RTT with the assumption that it is either an indication of congestion or of excess capacity in the bottleneck link. Since the protocols try to sustain a buffer occupancy at approximately a constant level, a new flow could easily overestimate the propagation delay by mistakenly including a constant queueing delay in the measured minimum RTT when it starts. This overestimation eventually causes unfairness, known as the persistent congestion problem, among contending flows as the sender assumes the link being less congested than what it actually is. Many methods have been proposed to correct this problem [START_REF] La | Issues in TCP Vegas[END_REF][START_REF] Low | Understanding TCP vegas: a duality model[END_REF][START_REF] Chan | Performance improvement of congestion avoidance mechanism for TCP Vegas[END_REF][START_REF] Tan | FAST TCP: fairness and queuing issues[END_REF] yet almost all of them rely on intermediate routers to be upgraded and thus redeployed. A few other attempts to solve the problem without support from the queuing management mechanisms in routers, have been presented in [START_REF] Cui | Improving the fairness of FAST TCP to new flows[END_REF][START_REF] Rodríguez-Prez | The persistent congestion problem of FAST-TCP: analysis and solutions[END_REF] under certain limitations such as having large enough and homogeneous propagation delays, not too many simultaneous flows, and no uncontrolled cross traffic.

A DCA protocol: FAST-TCP

FAST-TCP is the most representative DCA protocol that achieves higher throughput, lower latency and fewer packet drops compared to previous versions of TCP. Loss based protocols such as TCP Reno and its variants drive the network to congestion so that they can receive the feedback they need in order to adjust the size of their congestion windows. In contrast, TCP protocols with delay based congestion avoidance mechanisms, such as TCP Vegas and FAST-TCP, keep an estimate of the round trip propagation delay, which is the minimum RTT observed throughout a single connection, to track changes in the queuing delay by measuring the RTT continuously. The queue length is estimated by measuring the difference between the observed RTT and the estimated propagation delay. FAST-TCP is an enhanced version of TCP Vegas that does not penalize the flows with large bandwidth-delay products and that has good convergence properties. FAST-TCP also differs from TCP Vegas the way the rate is adjusted when the number of packets stored is too small or large. TCP Vegas makes fixed size adjustments, independently of how far it is from the equilibrium point. FAST-TCP takes larger steps when the system is far away from the equilibrium and smaller steps otherwise to improve the speed of convergence and stability.

FAST-TCP implements a learning procedure consisting of estimating the propagation by the minimum observed RTT (plus some filters) and this has been modelled accurately in [START_REF] Jacobsson | Dynamic Modeling of Internet Congestion Control[END_REF]. One additional feature of FAST-TCP is independence of the propagation delays in equilibrium; hence sources with large propagation delays are not penalized as is usually the case for classical implementations of TCP. The congestion window update law explicitly depends on both the queuing and the propagation delays [START_REF] Wei | FAST TCP: motivation, architecture, algorithms, performance[END_REF] in order to achieve fairness even in the case of heterogeneous propagation delays.

Analysis of The Ideal Case

In this section some preliminary results from [START_REF] Briat | Nonlinear state-dependent delay modeling and stability analysis of internet congestion control[END_REF] are recalled. We assume that both propagation and queuing delays are perfectly known (ideal case).

We consider here the following continuous-time fluid-flow nonlinear model, very often used to analyze the behavior of a single-bottleneck network (with unlimited queue length) with N users using FAST-TCP [START_REF] Jacobsson | Dynamic Modeling of Internet Congestion Control[END_REF][START_REF] Briat | Nonlinear state-dependent delay modeling and stability analysis of internet congestion control[END_REF]:

τ (t) = 1 c N i=1 xi(t-T f i ) τ (t)+Ti + δ(t) -1 (1) ẋi (t) = γ - τ (g(t-T b i )) Ti+τ (g(t-T b i )) x i (t) + α i , i = 1, . . . , N (2)
where x i , τ , c, T i = T f i + T b i , T f i and T b i are the window size of user i, the queuing delay, the buffer output capacity, the total constant propagation delay of source i and the forward and backward constant propagation delays of source i respectively. The disturbance term δ represents the normalized cross-traffic modeling unregulated flows and non-FAST-TCP flows such as the usual TCP. The terms γ and α i are protocol tuning parameters, the first one acts on the speed of reaction of the protocol (the bandwidth, in the control theoretic sense) and α i is the desired number of enqueued packets at equilibrium. The function g(•) is the inverse function of f (t) = t + τ (t) as defined in [START_REF] Briat | Nonlinear state-dependent delay modeling and stability analysis of internet congestion control[END_REF] and allows to write the overall network rigorously as a nonlinear time-delay system with statedependent delay. The unique equilibrium point of this a model is given by:

τ * = i αi c(1-δ * ) , x * i = α i 1 + Ti τ * and φ * i = = αi τ * (3)
where φ * i denotes the flow of source i at equilibrium, i = 1, . . . , N . From the above result we can see that the equilibrium is both proportionally-fair and efficient [START_REF] Srikant | The Mathematics of Internet Congestion Control[END_REF][START_REF] Sandberg | On performance limitations of congestion control[END_REF]. The equilibrium flows do not depend on the propagation delays, hence sources with large propagation delays are not penalized.

Since the theoretical local/global stability analysis of the nonlinear model ( 1)-( 2) is a very difficult still open problem, we will restrict the analysis to the single source problem (i.e. N = 1). Using results from time-delay systems theory [START_REF] Gu | Stability of Time-Delay Systems[END_REF][START_REF] Niculescu | Delay effects on stability. A robust control approach[END_REF][START_REF] Michiels | Stability and stabilization of time-delay systems. An eigenvalue based approach[END_REF][START_REF] Briat | Nonlinear state-dependent delay modeling and stability analysis of internet congestion control[END_REF] and robust analysis [START_REF] Zhou | Robust and Optimal Control[END_REF][START_REF] Gu | Stability of Time-Delay Systems[END_REF], the following theorem is proved in [START_REF] Briat | Nonlinear state-dependent delay modeling and stability analysis of internet congestion control[END_REF]:

Theorem 1 (Network Local Stability [START_REF] Briat | Nonlinear state-dependent delay modeling and stability analysis of internet congestion control[END_REF]). Let us consider the network model ( 1)-( 2) with single user. Then the equilibrium point (x * , τ * ) is 1. locally delay-independent stable if and only if τ * > T . 2. locally delay-dependent stable if τ * < T and τ * (T -1) + T 2 ≤ 0.

locally delay-dependent stable if τ

* < T , τ * (T -1) + T 2 > 0 and γ < 1 τ * (T -1)+T 2 .
In the subsequent sections, the impact of the unperfect knowledge of the queuing delay value on the overall network stability will be studied.

Learning the queuing delay

In the FAST-TCP protocol implementation, the propagation delays are estimated as the minimal observed RTTs: Ti (t) := inf s∈[ti,t] {RT T i (s)} where the RTT is RT T i (t) := T i + τ (g(t -T b i )), Ti (t) is the estimated propagation delay for source i at time t and t i is the arrival time of source i in the network. So, the sources learn their propagation delays through an iterative process using the RTT measurements. The actual advantage of such a procedure lies in its simplicity: only the senders' routines need to be modified, the entire infrastructure (routers/servers) remains unchanged. However, according to the scenario, the sources may be unable to estimate their propagation delay accurately, resulting in an underestimation of the queueing delays and a loss of fairness. The only way to observe the actual propagation delay is to communicate when the queueing delay is 0. However, DCA protocols have an antagonist effect since they strive to maintain a non-zero queue for efficiency and flow fairness.

In order to take into account the learning process in the analysis, the protocol model ( 2) is refined to

ẋi (t) = γ -x i (t) + Ti+εi(t) τ (g(t-T b i ))+Ti x i (t) + α i (4)
where the learning errors ε i (t) are defined by

ε i (t) = Ti (t) -T i ≤ τ (g(s - T b i ))
. Since ε i (t) can be anything according to the scenario, we will rather focus on asymptotic properties (equilibrium points and local stability) of the above protocol model for any possible values for the errors at equilibrium.

Impact on the equilibrium point

Solving for the equilibrium points for (1)-( 4) yields the expressions:

x * i = αi(Ti+τ * ) τ * -ε * i , φ * i = αi τ * -ε * i and ε * i < τ * (5)
where the ε * i 's are the estimation errors at equilibrium and the delay at equilibrium τ * solves

N i=1 φ * i -c(1 -δ * ) = 0. ( 6
)
From the above equations, we can clearly see that when the errors at equilibrium for each source are different, then proportional-fairness cannot be achieved. Hence, fairness is only reachable under the very strong assumption of exact knowledge of all the propagation delays. The equation ( 6) defining the equilibrium delay can be rewritten as the polynomial equation P N (τ ) = 0 where

P N (τ ) := N i=1 α i N j =i (τ * -ε * j ) -c(1 -δ * ) N i=1 (τ * -ε * i ) (7)
and for which only the nonnegative solutions must be considered.It is well known that, in general, there is no analytical solutions to P N (τ ) = 0 when N is large. Hence we will restrict the analysis to simple cases where analytical results can be obtained.

Equilibrium points analysis -Single source case In the single source case, the equilibrium queuing delay is given by τ * = α c(1-δ * ) + ε * which is nothing but a simple shift of the ideal equilibrium (3) leading to an increase of the queuing delay. When ε * → 0, we recover the equilibrium point of the ideal case.

Equilibrium points analysis -Two sources case In the 2-sources case, the equilibrium delay is defined by the following polynomial

P 2 (τ ) = -η 2 τ 2 +η 1 τ -η 0 with η 2 = c(1 -δ * ), η 1 = α 1 + α 2 + η 2 (ε * 1 + ε * 2 ) and η 0 = η 2 ε * 1 ε * 2 + α 1 ε * 2 + α 2 ε * 1 .
Since by definition, we have c, δ * , α i , ε * i > 0, i = 1, 2 then η 2 > 0, η 1 > 0 and η 0 > 0. Hence, the real part of the roots of P 2 are positive. To see that the solutions are all real, it is easy to show that the discriminant ∆ := η 2 1 -4η 2 η 0 is positive. Thus, the network admits 2 positive equilibrium points given by

τ * = τn 2 + ε1+ε2 2 ± √ ∆ 2c(1-δ * ) (8)
where τ n = α1+α2 c(1-δ * ) is the equilibrium delay in the ideal case. So, in the two sources problem, an overestimation of the propagation delays leads to the creation of two distinct positive queueing delay equilibrium points. Note also that the solutions τ * → τ n as ε 1 , ε 2 → 0 (the zero limit disappears due to a pole/zero cancellation). 1 where we establish a FAST TCP connection between each source S i , and its corresponding destination D i . We assume that the packets carry a payload of 1000 bytes and that the maximal queue size is chosen to be sufficiently large to avoid packet dropping. In the considered scenario, we assume that the two flows arrive consecutively. The first one comes at time t = 10 seconds, when the queue is empty. Hence the first source can estimate exactly its propagation delay, so ε * 1 = 0, and the queuing delay converge to the equilibrium value τ * 1 = α/η where η = c(1δ * ). Then the second flow comes at t = 30 seconds and makes the queue length increase, hence the minimal measured RTT for the second source is the one measured at t = 30 seconds, hence we have ε 5 whose sum equals η, showing then efficient but unfair (φ * 1 < φ * 2 ) equilibrium. The simulation of the topology in Figure 1 is performed with the NS-2 simulator and the obtained results are gathered in Table 1 with a comparison with the theoretical results of Section 5.1. Two scenarios are considered, the first one considers homogeneous propagation delays and no cross-traffic while the second adds a cross-traffic of 20Mb/s.

We can see that, for the considered scenarios, the windows size, the queuing delay and the queue length are quite well predicted. Fig. 2 shows the rate evolution of the sources in the scenario without cross-traffic. As also noticed in [START_REF] Rodríguez-Prez | The persistent congestion problem of FAST-TCP: analysis and solutions[END_REF], the flows fail to converge to a fair equilibrium.

Impact on the stability of the equilibrium point

It is interesting to study the local stability of the equilibrium points to answer the question on the protocol stability at an unfair equilibrium point. To this aim, the following linearized model from (1)-( 4) is devised:

ẏi (t) = -γ ε * i -τ * Ti+τ * y i (t) -γ (Ti+ε * i )x * i (Ti+τ * ) 2 ν(t -T i -τ * ) ν(t) = i 1 c(Ti+τ * ) y i (t) -i x * i c(Ti+τ * ) 2 ν(t) + 1 c ζ(t) (9)
where

y i (t) := x i (t) -x * i , ν(t) := τ (t) -τ * and ζ(t) := δ(t) -δ * .
Restricting us to the single user case, we get the following theorem for delay-independent stability: Theorem 2. The system [START_REF] Jacobsson | Dynamic Modeling of Internet Congestion Control[END_REF]

is locally delay-independent stable if and only if the inequality ε

* < α c(1-δ * ) -T holds.
Proof. The proof is similar to as the one of [START_REF] Briat | Nonlinear state-dependent delay modeling and stability analysis of internet congestion control[END_REF]Theorem 4.3].

Since ε * ≥ 0 then in order to tolerate positive errors, the right-hand side must be at least positive. Based on this, we can conclude that the error has a negative impact on the stability. By extension, the same problem will occur in more complex topologies.

Whenever delay-independent stability is not achieved we have the following theorem: Theorem 3. The system ( 9) is delay-dependent stable if one of the following conditions hold:

1. T + ε * - α c(1-δ * ) 2 < 0; or 2. T + ε * - α c(1-δ * ) 2 ≥ 0 and γ < c(1-δ * ) 2 c(T +ε * )(1-δ * ) 2 -α .
Proof. The proof is identical as for Theorem 1; see [START_REF] Briat | Nonlinear state-dependent delay modeling and stability analysis of internet congestion control[END_REF].

According to the above results, we can conclude that the stability can be ensured through an appropriate choice of the tuning parameter γ similarly as in the ideal case. Additionally, the error term penalizes the maximal admissible speed of the protocol and has thus an impact on the overall efficiency of the network. Conversely, if the term γ is not chosen in order to consider the eventual error term, stability may be lost.

Measuring the queuing delay -Case study

The second solution to the estimation of both queuing and propagation delays consists of an explicit feedback of the queuing delays by the routers. In such a framework, part of the header of the packet is dedicated to contain the sum of all the queueing delays the packet has experienced over its path. Thus, the source gets an explicit value for the total queuing delay and can subtract it from the measured RTT to compute the propagation delay. This solution needs, however, an update of all routers to add this feature. It is hence less simple to deploy than the estimation procedure for the queuing delay that is solely based on RTT measurements. Moreover, since the size of the packet header is constant, the measured aggregate queuing delay is stored with fixed precision and a measurement error is consequently introduced. Therefore, an analysis of the influence of the errors on the equilibrium points and on the stability deserve to be studied. Interestingly, the protocol model incorporating the use of a quantized measure of the queuing delay is very similar to as the one incorporating the learning error:

ẋi (t) = γ -τ (g(t-T b i ))-εi(g(t-T b i )) τ (g(t-T b i ))+Ti x i (t) + α i (t) . (10)
However, in the present case, the error term satisfies |ε i (•)| ≤ q/2 where q is the resolution of the quantizer. The only differences lie in the sign of the errors which are not restricted to be positive and in the boundedness of the errors. Indeed, the worst case error only depends on the choice of the quantization step while in the previous case, the worst case error was depending on the state of the network.

Impact on the equilibrium point

At equilibrium, the queuing delay is constant and hence the quantization error is identical for all users, i.e. ε i = ε * , i = 1, . . . , N . This an important property of the current approach. Indeed, simple computations yield:

x * i = α i Ti+τ * τ * -ε * , φ * i = αi τ * -ε * and τ * = i αi c(1-δ * ) + ε * . (11)
In such a case, the equilibrium point is unique, efficient and proportionally fair. This was not the case with the learning strategy due to the imbalance between the errors. This is one of the benefits of the approach.

Impact on the stability

Similarly to as previously, we will consider the single user problem. We will first assume that ε * = 0 to avoid complex calculations. A discussion will be provided for the case ε * = 0. When the quantization error is 0 at equilibrium, the quantization function ϕ(•) is an odd function which belongs to the sector (0, 2), i.e. we have 0 ≤ ϕ(s) s ≤ 2 for any s ∈ R. A lot of works have been devoted to the analysis of linear systems interconnected to sector nonlinearities [START_REF] Lur'e | On the theory of stability of control systems[END_REF]. The problem can be rewritten as the negative feedback interconnection of ϕ(•) and

F (s) = µ 3 ξ2ψ1e -s(τ * +T ) (s+µξ1)(s+µξ3) .
A very important result for the stability analysis of such interconnections is called the circle criterion and consists of a generalization of the Nyquist criterion: Theorem 4 (Circle Criterion). Let us consider an interconnection (with negative feedback) of an asymptotically stable system F (s) and a nonlinear element ϕ(•) satisfying the sector condition (k 1 , k 2 ). The interconnection is asymptotically stable if the graph of F (jω) with ω ∈ R does not enter the circle passing through the points -1/k 1 and -1/k 2 in the complex plane.

In the considered case, the 'circle' coincides with the vertical plane passing through the point -1/2 in the complex plane. It is easy to show that the circle condition is equivalent to show that F (jω) does not encircle the point -1/2 in the complex plane. This actually consists in a scaling of the Nyquist criterion and is equivalent to the stability of F2 (s) = 2N (s) D(s)+2N (s) where F (s) = N (s)/D(s). Since the structure of the quasipolynomial D(s) + 2N (s) is very similar to as in the ideal case, the same approach is used and yields the lemma: Theorem 5. Assuming that the quantization error at equilibrium is 0, then the equilibrium point (x * , τ * ) of system ( 1)-( 10) is 1. locally delay-independent stable if τ * > 2T . 2. locally delay-dependent stable if τ * < 2T and 2T (T + τ * )τ * ≤ 0.

locally delay-dependent stable if τ

* < 2T and 2T (T + τ * ) -τ * > 0 and γ < 1 2T (T +τ * )-τ * .
Proof. The proof follows the same lines as for the other results; see [START_REF] Briat | Nonlinear state-dependent delay modeling and stability analysis of internet congestion control[END_REF].

We can conclude on the fact that, in the case ε * = 0, the tuning term γ can be chosen in order to avoid oscillations. We explain now why this is not possible in the general case ε * = 0.

Indeed, when ε * = 0, the quantization function is not odd anymore since it must be horizontally shifted to be centered around the equilibrium point. Therefore the sector takes the more general form (0, θ) where θ is defined by θ := 2(1 -2|κ|) -1 where ε * = κq, κ ∈ [-1/2, 1/2]. Hence, the term θ can reach arbitrarily large values, translating then the 'circle' horizontally to the right. When the error is maximal (κ = ±1/2), the forbidden area of the complex plane is the entire open left-half plane itself. Due to the exponential term of F (s), then the graph of F (jω), ω > 0 always enters the open left-half plane and thus limit cycles cannot be avoided.

Conclusion

In this paper, we have addressed the fairness and stability properties of delay based transmission control protocols; in particular FAST-TCP. The update law of FAST-TCP congestion windows requires to know both the propagation and queuing delays if fairness and efficiency are to be provided. We have incorporated two approaches to estimate the propagation delay using the model we developed for such protocols.

The first approach, which is also the one implemented in FAST-TCP, employs an iterative learning process to estimate the propagation delay as the minimal observed RTT. The propagation delay is always overestimated in this case unless the queuing delay drops to zero. It is shown that such estimation procedure leads to loss of fairness due to diverse estimation errors at each source along with multiple equilibrium points for the queuing delay. We have developed a model for the delay based congestion avoidance protocols to analyze the impact of the queuing delay estimation error on equilibrium and its stability. Using this model, we have observed that the stability of the equilibrium points, in the single-source case, can be ensured through an appropriate choice of the tuning term γ of the protocol. The developed model, which is able to predict the congestion window size, the queuing delay and the number of enqueued packets quite accurately, is validated by running NS-2 simulations.

The second approach we have analyzed is based on the assumption that the routers feedback a quantized measure of their queuing delay. Hence both propagation and queuing delays (modulo the quantization error) can be estimated easily. We have shown that this strategy manages to preserve the uniqueness of the equilibrium point as well as fairness, yet it can not prevent limit cycles (oscillations) around the equilibrium points for which the quantization error is too large.

Fig. 1 :

 1 Fig. 1: Network Topology used for Simulation Example 1. Let us consider the topology depicted in Fig.1where we establish a FAST TCP connection between each source S i , and its corresponding destination D i . We assume that the packets carry a payload of 1000 bytes and that the maximal queue size is chosen to be sufficiently large to avoid packet dropping. In the considered scenario, we assume that the two flows arrive consecutively. The first one comes at time t = 10 seconds, when the queue is empty. Hence the first source can estimate exactly its propagation delay, so ε * 1 = 0, and the queuing delay converge to the equilibrium value τ * 1 = α/η where η = c(1δ * ). Then the second flow comes at t = 30 seconds and makes the queue length increase, hence the minimal measured RTT for the second source is the one measured at t = 30 seconds, hence we have ε * 2 = τ * 1 . Solving for the delay equilibrium points when both flows are active we get τ * 2 = α 2η 3 ± √ 5 which are both positive. Solving now for the flows, we get φ * 1 = 2η

* 2 = τ * 1 .

 1 Solving for the delay equilibrium points when both flows are active we get τ * 2 = α 2η 3 ± √ 5 which are both positive. Solving now for the flows, we get φ * 1 = 2η 3+ √ 5 and φ * 2 = 2η 1+ √

1 :Fig. 2 :

 12 Fig.2: Rates evolution for Source 1 (plain) and Source 2 (dashed) (no cross-traffic)