System for transmitting data packets according to a multiple access protocol

Abstract

A system for transmitting data packets includes at least one access point and at least one terminal. The access point receives data packets transmitted by the terminal in compliance with a multiple access protocol including carrier detection, and transmits to the terminal at least the width of the contention window that the terminal is to observe for transmitting a packet. The transmitted packets are coded using an erasure code and the access point is further adapted to decode the received packets. The system may be applied to networks such as WLANs.

Claims

1. An access point comprising: a processor; and a non-transitory computer-readable data medium comprising instructions of a computer program stored thereon, which when executed by the processor configure the access point to: transmit to at least one terminal at least a width of a contention window that said terminal is to observe for transmitting a packet on a channel after expiration of a fixed time interval during which the terminal observes that the channel is free; receive data packets transmitted by said terminal in compliance with a multiple access protocol, the multiple access protocol including carrier detection and taking into account said width of the contention window, and wherein said transmitted packets are coded using an erasure code, each coding operation with the erasure code being applied on n successive packets to recover erased packets, wherein n denotes a length of the erasure code; and decode the received data packets.

2. The access point according to claim 1, wherein the instructions further configure the access point to transmit to said terminal at least one parameter of said erasure code.

3. The access point according to claim 1, wherein said width of the contention window transmitted by the access point is a function at least of a minimum distance of said erasure code and of a total number of terminals connected to said access point.

4. The access point according to claim 1, wherein the erasure code has a minimum distance d, and enables the access point to correct at least all configurations of erased packets up to (d1) erased packets.

5. A terminal comprising: a processor; and a non-transitory computer-readable data medium comprising instructions of a computer program stored thereon, which when executed by the processor configure the terminal to: receive, from an access point, at least a width of a contention window that the terminal is to observe for transmitting a packet on a channel after expiration of a fixed time interval during which the terminal observes that the channel is free; and transmit data packets to said access point in compliance with a multiple access protocol, the multiple access protocol including carrier detection and taking into account said width of the contention window, and wherein the transmitted packets are coded by an erasure code, each coding operation with the erasure code being applied on n successive packets to recover erased packets, wherein n denotes a length of the erasure code.

6. The terminal according to claim 5, wherein the instructions further configure the terminal to receive from said access point at least one parameter of said erasure code, and taking account thereof.

7. The terminal according to claim 5, wherein the erasure code has a minimum distance d, and enables the access point to correct at least all configurations of erased packets up to (d1) erased packets.

8. A non-transitory computer-readable data storage medium comprising computer program code instructions stored thereon for managing operation of an access point when the instructions are executed by a processor of the access point, wherein the instructions configure the access point to: transmit to at least one terminal at least a width of a contention window that said terminal is to observe for transmitting a packet on a channel after expiration of a fixed time interval during which the terminal observes that the channel is free; receive data packets transmitted by said terminal in compliance with a multiple access protocol, the multiple access protocol including carrier detection and taking into account said width of the contention window, and wherein said transmitted packets are coded using an erasure code, each coding operation with the erasure code being applied on n successive packets to recover erased packets, wherein n denotes a length of the erasure code; and decode the received data packets.

9. The non-transitory computer-readable data storage medium according to claim 8, wherein the erasure code has a minimum distance d, and enables the access point to correct at least all configurations of erased packets up to (d1) erased packets.

10. A non-transitory computer-readable data storage medium comprising computer program code instructions stored thereon for managing operation of a terminal when the instructions are executed by a processor of the terminal, wherein the instructions configure the terminal to: receive, from an access point, at least a width of a contention window that the terminal is to observe for transmitting a packet on a channel after expiration of a fixed time interval during which the terminal observes that the channel is free; and transmit data packets to said access point in compliance with a multiple access protocol, the multiple access protocol including carrier detection and taking into account said width of the contention window, and wherein the transmitted packets are coded by an erasure code, each coding operation with the erasure code being applied on n successive packets to recover erased packets, wherein n denotes a length of the erasure code.

11. The non-transitory computer-readable data storage medium according to claim 10, wherein the erasure code has a minimum distance d, and enables the access point to correct at least all configurations of erased packets up to (d1) erased packets.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) Other aspects and advantages of the invention appear on reading the following detailed description of particular embodiments, given as non-limiting examples. The description refers to the accompanying figures, in which:

(2) FIG. 1 is a diagram of the durations conventionally involved in the CSMA/CA protocol;

(3) FIG. 2 shows the format of data packets in an implementation of the invention;

(4) FIG. 3 shows code words being constructed from a set of data packets, in an implementation of the invention;

(5) FIGS. 4 to 7 show as a function of the number of users the mean aggregated throughput in the absence of coding and in the presence of coding, and the rate of deleted packets and of non-correction after decoding by a user, for various codes and for different widths of the contention window;

(6) FIG. 8 applies to a code of length 255 and a number of users equal to ten, and shows the aggregated throughput as a function of the width of the contention window and the dimension of the code; and

(7) FIG. 9 applies to a code of length 255 and a number of users equal to ten, and shows the aggregated throughput as a function of the width of the contention window, for three values for the dimension of the code.

DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENTS

(8) Consideration is given to a set of user terminals suitable for transmitting data packets to a certain access point using a multiple access protocol, such as the CSMA/CA protocol described briefly above. By way of example, these terminals and the access point may form part of a wireless local area network (WLAN), e.g. of the WiFi type.

(9) With reference to FIG. 1, the description begins with a few reminders about the durations that are conventionally involved in the CSMA/CA protocol.

(10) In FIG. 1: T.sub.packet is the transmission duration of a packet; SIFS (stands for short interframe space) is a time interval before a transmission is followed by an acknowledgment (by default, the SIFS is 10 microseconds (s); T.sub.ack is the duration of an acknowledgment (by default, T.sub.ack is 2 s): if a user has not received an acknowledgment after a time interval (SIFS+T.sub.ack) after transmitting a packet, the packet is considered as lost; DIFS (stands for distributed interframe space) is the above-mentioned (fixed) time interval before which a user seeing that the channel is unoccupied can start the above-mentioned backoff duration (by default DIFS is 50 s); and the backoff duration: in order to avoid all users starting to transmit at the end of the DIFS, this random duration is added that is an integral multiple of a duration increment T.sub.slot (20 s by default); as mentioned above, the backoff duration is determined randomly by each user within the contention window, written W below, and it is expressed as a number of time slots.

(11) In the invention, the packets transmitted by users are coded by means of one (or more) erasure codes that are themselves known. The code to be used is determined by the access point as a function of the number of users communicating therewith.

(12) In an embodiment, the access point transmits to each user, at least after the terminal has connected with the access point, the dimension k of the code, together with the width W of the contention window to be compiled with by the user, or merely the width W of the contention window when all of the users are using the same code (e.g. a code having parameters that are standardized).

(13) There follow a few reminders about packet coding.

(14) It is assumed that all of the packets transmitted at the same size and contain L symbols of m bits each, as shown in FIG. 2. In an implementation, the coding operation is performed transversely on a number n of successive packets {P.sub.1, P.sub.2, . . . , P.sub.n}, so that each of the L columns containing n symbols of m bits each forms a code word of length n and of dimension k, as shown in FIG. 3.

(15) For m=1, a binary code . . . is used capable of providing erasure corrections; for this purpose, it suffices to consider the parity control matrix of the code, since each parity equation of the code, which is of the form:
h.sub.1x.sub.1+h.sub.2x.sub.2+ . . . +h.sub.nx.sub.n=0(1)
where h.sub.i{0,1} and x.sub.i {0,1} for i=1, . . . , n also applies to the packets:
h.sub.1P.sub.1+h.sub.2P.sub.2+ . . . +h.sub.nP.sub.n=0(2)
where 0 is the packet in which all of the bits are zero, and addition is the XOR function applied bit by bit to the packet.

(16) For m>1, it is preferable to use a code defined on an extension field GF(2.sup.m), e.g. GF(2.sup.7) or GF(2.sup.8) depending on whether m=7 or m=8. Under such circumstances, the parity equation (2) involves arithmetic in this extension field, in particular multiplication. The codes are then Reed-Solomon (RS) codes. The decoding of each code word on a column can be performed either on the basis of these parity equations, or by using any other decoding algorithm that is used for RS codes (e.g. algebraic decoding).

(17) The parameters to be taken into account for choosing the code are the following in particular.

(18) The important parameter of a linear code, whether or not it is binary, is the minimum number of symbols by which two different code words differ; this quantity is written d and referred to as the minimum distance of the code. The parameters n, k, and d are not independent, but are constrained by a certain number of inequalities, including the Singleton bound:
dnk+1(3)

(19) When the inequality is reached (d=nk+1), it is said that the code is maximum distance separable (MDS). In the binary configuration, it is found that the only MDS codes are trivial codes: a repeated code (a packet is repeated (n1) times), or a parity code in which only one parity packet is added after (n1) independent data packets). In order to have codes that are not trivial and that provide better performance, it is necessary to work in the above-mentioned finite fields; in this context, a conventional example of an MDS code is specifically that of the above-mentioned RS codes. The invention is thus preferably performed using an MDS code over GF(2.sup.m) with m>1.

(20) In order to evaluate performance, it is assumed that all of the erasure configurations up to (d1) erasures are corrected, and that all configurations of d erasures or more are not corrected (which is pessimistic, since some such configurations are corrected, but this phenomenon is ignored below). It is therefore advantageous to have the minimum distance d as great as possible for given values of n and k, which shows the importance of MDS codes in this perspective.

(21) An implementation of the invention is described below.

(22) In this implementation, a Reed-Solomon code is used, and for reasons of ease of implementation, it is preferable to select codes on GF(2.sup.8); the codes may be shortened, i.e. they may be of a length n<255 bytes.

(23) Also preferably, a code rate k/n is selected that is adapted to the channel as seen by the terminals. Specifically, it would be sub-optimal to use a fixed code rate, since under most circumstances such a code would be either too powerful, or else not powerful enough; if the code rate is too small, then redundancy is introduced pointlessly and the available data rate is poorly used; conversely, if the code rate is high, the code is inefficient and is not capable of correcting all of the erasures.

(24) In order to reduce the rate of packet loss, it is necessary to increase the width W of the contention window: the (backoff) durations of each user can then take greater values (thus giving a longer time interval between two packet transmissions). There are few collisions since the number of users is small, since there is low probability that two or more will draw the same value for the backoff duration, the correcting code has poor efficiency, and the drop in aggregated throughput is due mainly to the code rate of the correcting code. As the number of users increases, the number of collisions to which each user is subjected also increases, however if the overall correction capacity of the code is not exceeded, the aggregated throughout will continue to increase. Thereafter, at a certain point, the number of collisions begins to exceed the correction capacity; the coding can then no longer recover deleted packets, and the aggregated throughput decreases.

(25) In a slightly simplified version of the CSMA/CA protocol, this qualitative analysis can be made more precise by the following qualitative analysis. For this purpose, it is assumed that the users always have a packet for transmission, such that in each contention period, all of the users attempt to access the resource; the aggregated throughput can thus reach its theoretical maximum (under saturated or full-buffer conditions).

(26) The probability of a given user i being subjected to a collision during a contention period is given by:

(27) $\begin{array}{cc}{p}_{\mathrm{coll}}=\frac{1}{W}& \left(4\right)\end{array}$

(28) It can be shown that the probability of a given user i among N accesses the channel because that user drew the smallest backoff duration (but without any guarantee of being the only user to draw it, so there is still some possibility of collision), is given by:

(29) $\begin{array}{cc}{p}_{\mathrm{access}}=\underset{k=0}{\overset{W-1}{.Math.}}\frac{1}{W}{\left(1-\frac{k}{W}\right)}^{N-1}& \left(5\right)\end{array}$

(30) It can be deduced therefrom that the probability of erasure is given by:

(31) $\begin{array}{cc}p=\frac{1}{{.Math.}_{k=0}^{W-1}{\left(1-\frac{k}{W}\right)}^{N-1}}& \left(6\right)\end{array}$

(32) In the absence of coding, the aggregated throughput for N users is thus given by:
D.sub.NC=Np.sub.win/(7)
where is the mean time interval between two transmissions, and where:

(33) $\begin{array}{cc}{p}_{\mathrm{win}}=p_{\mathrm{access}}-\frac{1}{W}& \left(8\right)\end{array}$
is the probability of a transmission being successful for any one of the N users.

(34) In the presence of a code of length n, of dimension k and of minimum distance d, the maximum correction capacity of the code is (d1) deleted packets. The probability of there being at most (d1) erasures over n packets is given by:

(35) $\begin{array}{cc}{p}_{\mathrm{OK}}=\underset{k=0}{\overset{d-1}{.Math.}}{C}_n^k{p^k\left(1-p\right)}^{n-k}& \left(9\right)\end{array}$
which is the probability of successfully decoding a code word of n packets, including k packets of information. The aggregated throughput in the presence of coding is thus given by:

(36) $\begin{array}{cc}{D}_C=N\frac{k}{n}{p}_{\mathrm{acc}}{p}_{\mathrm{OK}}\text{/}& \left(10\right)\end{array}$

(37) These results are illustrated below by means of a few numerical values. FIGS. 4 to 7 apply to a number of users N lying in the range 1 to 40, and they show: the mean aggregated throughput (expressed in packets per second (packets/s)) in the absence (smooth curve) and in the presence (curves with bold dots) of correcting coding; and the rate at which packets are deleted in the absence of coding (smooth curve) and the rate of non-correction after decoding (curve with bold dots), per user.

(38) In a first example, shown in FIG. 4, consideration is given to the code (n=255, k=200, d=56), and it is assumed that W=32 slots. In this figure, it can be seen that for n<6, the failure rate for correcting erasures is less than 1%; a loss of throughput is observed only as a result of the 200/255 rate of the code. Once N7, the correction capacity of the code is exceeded, decoding fails more often, and the failure rate becomes greater than the erasure rate in the absence of coding.

(39) In a second example, shown in FIG. 5, the same code is used, but with W=50 slots. It is now possible to ensure a failure rate of less than 1% for up to nine users.

(40) In a third example, shown in FIG. 6, the same code is used again, but with W=100 slots. This time, it is possible to accept 17 users with a failure rate of 1% after decoding. For a small number of users (fewer than five), the channel is poorly used since the contention window is too large and the collision rate in the channel is less than a few %. On increasing the number of users, the utilization of the channel is improved, and the additional collisions are remedied by means of the correcting code. Towards 20 users, the correction capacity of the code is exceeded, and the aggregated throughput collapses.

(41) In a fourth example, shown in FIG. 7, the same contention window W=100 slots is used as in the preceding example, but the code now has the following parameters (n=127, k=100, d=28). A very slight degradation in performance is observed since the code is shorter. The maximum aggregated throughput is reached with about 17 users.

(42) The above results suggest that it is possible to give an optimum value to the width W of the contention window if, conversely, it is assumed that the number of users competing for access to a given channel is known. Specifically, the existence of an optimum width W for the contention window is the result of a compromise: when the window is too small, there are too many collisions compared with the correction capacity of the code, erasures cannot be recovered and the throughput is zero. When W increases, there are fewer collisions, and decoding becomes effective. Thereafter, when W continues to increase, a stage is reached in which there are indeed hardly any collisions, but where the time delay between two packet transmissions becomes too long (the users space out their transmissions too much) and the aggregated throughput decreases.

(43) It is possible to optimize the aggregated throughput by acting simultaneously on the values of k and W when calculating the function D.sub.c(k,W) of equation (10) for a fixed number N of users. To do this, a table D is constructed in which each element (i,j) is equal to the aggregated throughput D.sub.c when: k=i, with 1in; and W=j, with 1jW.sub.max
(where W.sub.max is a maximum width for the contention window, arbitrarily fixed in this example at 200 slots), and a search is made for the pair (i*, j*), corresponding to the maximum for D(i,j).

(44) FIG. 8 is a graph representing D(k,W), for N=10 users and a code of length n=255.

(45) FIG. 9 applies to N=10 users and of length n=255, and shows the aggregated throughput as a function of the width of the contention window for three values for the dimension k of the code. In other words, FIG. 9 corresponds to three plane sections of FIG. 8, for three values of the parameter k: the optimum value (k=172) and the values k=150 and k=200.

(46) It can be seen that the maximum throughput, equal to 2967 packets per second, is reached for k=172 with a window of width W=32 slots. This throughput is greater than the value given in FIG. 9 for the other two values of k (150 or 200), values for which the maximum is also reached for different values of the parameter W, while being less than said maximum that is reached when k=172 and W=32 slots. It is thus advantageous to perform optimization simultaneously on both parameters k and W.

(47) Finally, it should be observed that the invention can be performed within nodes of a telecommunications network, e.g. transmitter terminals or access points of a WLAN, by using software and/or hardware components.

(48) The software components may be incorporated in a conventional computer program for managing a network node. That is why, as mentioned above, the present invention also provides a computer system. The computer system comprises in conventional manner a central processor unit using signals to control a memory together with an input unit and an output unit. Furthermore, the computer system can be used to execute a computer program comprising instructions for managing the operation of terminal or of an access point of the invention.

(49) Specifically, the invention also provides a computer program downloadable from a communications network and comprising instructions for managing the operation of a terminal or of an access point of the invention when the program is executed on a computer. The computer program may be stored on a computer-readable medium and may be executable by a microprocessor.

(50) The program may use any programming language, and it may be in the form of source code, object code, or code intermediate between source code and object code, such as in a partially complied form, or in any other desirable form.

(51) The invention also provides a non-removable or a partially or totally removable data medium that is readable by a computer and that comprises instructions of a computer program as mentioned above. The data medium may be any entity or device capable of storing the program. For example, the medium may comprise storage means such as a read only memory (ROM), e.g. a compact disk (CD) ROM, or a microelectronic circuit ROM, or magnetic recording means, such as a hard disk, or indeed a universal serial bus (USB) flash drive.

(52) Furthermore, the data medium may be a transmissible medium such as an electrical or optical signal, suitable for being conveyed by an electrical or optical cable, by radio, or by other means. The computer program of the invention may in particular be downloadable from an Internet type network.

(53) In a variant, the data medium may be an integrated circuit in which the program is incorporated, the circuit being adapted to execute or to be used in the management of a terminal or an access point of the invention.

(54) Although the present disclosure has been described with reference to one or more examples, workers skilled in the art will recognize that changes may be made in form and detail without departing from the scope of the disclosure and/or the appended claims.