Multiplex communications – Channel assignment techniques – Carrier sense multiple access
Reissue Patent
1998-05-14
2001-08-21
Ton, Dang (Department: 2661)
Multiplex communications
Channel assignment techniques
Carrier sense multiple access
C370S444000
Reissue Patent
active
RE037334
ABSTRACT:
The invention concerns computer networks which allow the exchange of information or “data” between different terminals.
Such a network conventionally comprises a transmission medium, generally an electrical or fiber optic cable. Stations or terminals are connected at various places on this cable, this connection being made through a “network interface”.
It is essential for the terminals to understand each other, despite their multiplicity. In some computer networks, a rule (multiplexing, token) is determined for this purpose, in accordance with which no more than one of the terminals may transmit over the communication medium at a given moment. Another technique permits “random access” to the network, that is to say several terminals may transmit at the same time. One consequence of this multiple access is that “collisions” may occur, and it will then be necessary to resolve them.
The ETHERNET (registered trade mark) network, governed by the standard known as IEEE 802.3, is of the random access type. The network management protocol is of the multiple access carrier sensing type with collision detection, or CSMA/CD (Carrier Sense Multiple Access with Collision Detection).
One of the essential features of such a network is its ability to effect a “collision resolution” rapidly. This is because, when a transmission has given rise to a collision, it is necessary to recommence transmission. This has the direct effect of increasing the instantaneous need for transmission. As a result, if a multiple access channel is operating with very high traffic, the collision resolution may take correspondingly longer, and consequently the waiting time for a successful transmission correspondingly more protracted.
The Applicant has moreover observed that at least two types of data traffic can be distinguished:
a) data coming from sensors in real time, for example voice (telephony) or video (image);
b) exchanges of files or knowledge tables coming from bulk storage, which are pure data packets.
The Applicant has also observed that the constraints which are applied to the exchange of these different types of data are fairly divergent.
Data coming from sensors in real time arm generally fairly heavily redundant. As a result it is possible to accept a significant loss rate for these data packets without appreciable degradation of the quality of the data conveyed: it is known for example that voice telephony data, which are highly redundant, may be cut to a great extent without loss of intelligibility. On the other hand, telephony data packets must be carried within strict time periods.
In contradistinction to this, exchanges of file data for example are much less sensitive to transmission times. On the other hand, they are not able to sustain any level of data loss and are very demanding in terms of passband. In addition, they require acknowledgement of reception and flow monitoring protocols, which is not the case with voice data packets for example.
This poses different problems, which the invention is aimed at helping to resolve.
A first aim of the invention is to provide a better collision resolution technique, which increases the efficacy of a multiple access channel.
The second aim of the invention is to allow the use and implementation of priority classes in the operation of this collision resolution technique.
In order to form a computer network from a transmission medium or channel, a device is associated with each data processing terminal, comprising:
a network interface, capable of the transmission/reception of messages over the channel, with monitoring of the channel in order to establish event signals, which selectively represent the direction of the start of a transmission on the channel, the detection of any new collision, and the detection of the return of the channel to the vacant state, and
a transmission/reception management device, for controlling the network interface in accordance with the event signals.
Means are provided, in general in the network interface, to ensure that, in the event of a collision, transmission is maintained (with indication of collision) for a sufficient length of time for all the stations concerned (within range of the stations which are the cause of the collision) to have detected this collision, after which all transmission is interrupted. As a result a “collision slot” is defined.
According to a first aspect of the invention, the device comprises a channel observation register which receives any event signal and in response establishes a channel observation signal, amongst a predetermined set of possibilities, this set comprising transmission (emission or reception), “collision slot”, or “vacant slot”, the collision time slot being made subject to a first minimum period (C), and the vacant slot existing only when the vacant channel state has lasted for a second minimum period (B) at least equal to the maximum outward and return propagation time for a signal on the channel and less than the first minimum period.
Consideration is now given to the time where the management device has a new packet to transmit, that is to say it receives a request to transmit a data packet. It then awaits a predetermined number (>=1) of refreshings of the state of the observation register (“refreshing” means change of state or reconfirmation of the same state). A first transmission attempt may or may not be enabled, depending on the observed sequence of change of state of the observation register. “Failure” means the cases where the attempt at transmission is not enabled or those where it results in a collision. In the event of failure, the management device reacts by initializing a current integer (E), to a value between a first (0) and a second (M−1) limit integer, inclusive. It then causes the current integer (E) to vary in accordance with a predetermined law, which is a function of the observation signal, or of sequences of values of this observation signal. It is preferably ensured that this sequence of observations does not go beyond the last attempt at transmission or the last failure indexed.
The predetermined law is preferably chosen as follows: it tends to move the current integer away from the first limit integer (0) if there is an abundance of collision slots; it tends to move it closer to it if there is an abundance of vacant slots. The word “abundance” here refers to the fact that it is possible to use any absolute or relative representation (average, for example) of the number of collision slots, or vacant slots, obtained over the interval of time in question.
When, the current integer (E) reaches the first limit integer (0), the device carries out a further observation of the channel in order to enable, or otherwise, a further attempt. In the event of failure, the device repeats the mechanism described above.
A person skilled in the art will understand that this collision resolution technique requires continuous observation of the channel only during two attempts to transmit any one packet. In other words, it does not require the maintenance at all times of a history, even partial, of the channel, upstream of the last attempt to transmit the packet concerned. This denotes the originality of the novel technique compared with the Ethernet collision resolution method (Binary Exponential Back-off) and the one described in French patent No 84 16 957, in the name of the Applicant, published under the No 2 597 686. This feature confers significant properties of robustness and efficacy on the technique proposed.
The initial value of the chosen integer (E) is preferably substantially random. It may be supplied by a pseudo-random generator operating on an integer of at least 10 bits, modulated by at least one integer of no more than 10 bits, specific to the terminal concerned, the result being referred to the interval of the limits of the said chosen integer (E).
According to a variant of the invention, the current integer is also taken closer to the first limit integer when there is a transmission without collision.
The invention may also be presen
Jacquet Philippe
Muhlethaler Paul
Foley & Lardner
Inria Institut National de Recherche en Informatique et en Autom
Ton Dang
LandOfFree
Data transmission device for random access network, with... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data transmission device for random access network, with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data transmission device for random access network, with... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2457693