Technical Field

This invention relates to communication systems and, more particularly, to a multiple access digital data communication system, apparatus, and method. Background of the Invention

In the early days of the telephone art, use of the telephone was often confined to communication among users within a local geographic area. As a result and over the years, the economies related to accessing a communication system have lead to telephones in a local area usually being interconnected through a central controller, often called a local central office in the art. As digital computers came upon the scene, another local community of use was discernible. Hence, a central controller is commonly employed for interconnecting various user terminals, or stations.

As the digital computer art advanced, parallel advances in the semiconductor art have lead to smaller, relatively inexpensive computers. With the advent of such smaller computers, the technique of central control is being abandoned in favor of a distributed control technique. Also, because of the usually bursty nature of digital computer information, the recent trend has also been toward communication systems having a capability for handling packets of digital information. One such distributed control communication system is disclosed in U. S. Patent 4,063,220. Such known systems are commonly called Carrier Sense Multiple Access/Collision Detection (CSMA/CD) Systems. Indeed, this patent discloses a communications system in which, when a terminal or a station or a source is to start an intended packet transmission on a communications channel, a phase decoder _listens to signals on the channel Jbefore transmitting

(LBT). Upon detecting the presence of another transmission

OMPI

on the channel, the terminal delays the intended transmission until no other transmissions are sensed, i.e., it waits for an ^ le channel (WIC) . When the intended transmission is started, the terminal thereafter listens to signals on the channel, i.e., it Hstens while transmitting (LWT) . If an interference (or collision) is detected, the transmission is terminated and a random number generator is used to schedule a retry by selecting an interval of time at the completion of which a retransmission of the packet will take place. Unfortunately known CSMA/CD systems do not effectively service both voice and data traffic. Usually, undesirable signal transmission delays may be introduced. Also, collisions being a problem, efforts are called for toward providing a communications system which mitigates the deleterious effects of collisions. Summary of the Invention

These and other problems are solved with the instant system, apparatus and method for controlling both digital voice traffic and digital data traffic in a communications system by taking into account periodicities typically present in voice traffic. By having a periodic source, such as a voice source, begin transmitting a packet after the periodic source has successfully acquired access to the channel and by having the voice packet include a preempt field, collisions are reduced. This fortuitously results in a decrease in the network delay. Channel contention iε further reduced by having the periodic source transmit all of the voice traffic, that has been priorly accumulated, whenever it transmits and, still further, to schedule its next transmission a predetermined time T _p after the termination of its last successful transmission. The Drawing

FIG. 1 illustrates a prior art communications system including a plurality of stations, also called terminals or sources in the art, interconnected by a communications channel, which system is useful in describing the principles of the invention;

>

FIG. 2 illustrates a typical aperiodic data traffic packet format useful in describing the principles of the invention;

FIG. 3 illustrates a periodic voice traffic packet format useful in describing the principles of the invention; and

FIG. 4 includes a flow chart useful in describing the principles of the invention, which flow chart illustrates features of the instant invention and which flow chart can readily be embodied in the system illustrated in FIG. 1. Detailed Description

Broadly, the instant method includes a protocol for transmitting signals of a first kind, here called periodic signals, as well as signals of a second kind, here called aperiodic signals, on a random access broadcast system, such as the system illustrated in FIG. 1. Periodic information can be typified as that commonly encountered with voice or speech signals, e.g., as between telephone users. Such signals, which are usually analog signals, can be straightforwardly processed by an analog-to-digital converter at a station. It is usually important that such periodic signals be transmitted without suffering an unacceptably long delay. A long delay could cause a voice signal to arrive at its intended destination too late to be used. One advantage of the instant method over known protocols is that, with the instant method, the maximum delay before a periodic packet can be transmitted without a collision iε the time elapsed during the transmitting of one aperiodic packet, which in turn does not exceed the time to transmit one periodic packet. On the other hand, aperiodic information can be typified as that commonly encountered with digital data signals, e.g., as between digital computers. Accordingly, the instant method can be used for controlling the transmission of data which does not occur periodically as well as the transmiεεion of data which doeε occur periodically. For ease of description and

OMΓI IPO

not by way of limitation, in the instant description, the aperiodic information is herein also referred to as data traffic while the periodic information is also referred to as voice traffic. Further, aperiodic packets are assumed to be of variable length. Also, periodic packets are assumed to be of fixed length. Still further, an aperiodic packet is assumed to be of a length which does not exceed the length of a periodic packet.

Referring to the illustrative syεtem structure shown in FIG. 1, bidirectional communicationε signal channel 10 is extended between terminators 20 and 30 and through each of a plurality of cascaded transmission couplers such as pasεive coupler 40-i. Bidirectional channel 10 may be embodied, for example, through a conventional high frequency coaxial or fiber optic cable. Each of terminators 20 and 30 may, for example, be a conventional impedance matching device for limiting reflections. Each of couplers 40-1 through 40-N may, for example, be a conventional T-connector which is insertable in path 10 εo that εignals to and from each respective one of sources, or stations, 30—1 through 30-N may be coupled to the communications link thereby formed. (Parenthetically, the words "station" and "source" and "destination" and "terminal" are used interchangeably herein.) In particular, on the one hand, coupler 40-i is for electrically coupling signals, representing, for example, packets of information, from communications channel 10 to station 30-i. In that manner, station 30-i may read (or receive) packets from communications channel 10. On the other hand, coupler 40-i is also for coupling signalε representing, for example, packets of information from station 30-i on communications channel 10. In that manner, station 30-i may write (or transmit) packets on communicationε channel 10. Station 30-i may include transceiver 111, interface εtage 115, and, aε a using device, station equipment 127. In turn, terminal equipment 127

include equipment such as a common telephone coupled through analog-to-digital and digital-to-analog converters and functioning as a voice source for providing digitized voice samples and for reconstructing an analog speech waveform, respectively. Alternatively, terminal equipment 127 could include a digital computer for providing digital data traffic. Also alternatively equipment 127 could include a digital interface unit, for example, for interconnecting channel 10 with one or more other such channels, some of the other channels perhaps being geographically or electrically distant from the instant channel. Obviously, εtill other alternatives will occur to the skilled artworker.

As an aside, it is common in the art that, when the stations are electrically relatively close to each other, e.g., within about two miles of each other, such an arrangement is referred to as, among other things, a local communications system or network or as a local digital loop. Thus, in line with the εtructure illustrated in FIG. 1, a plurality of local networks may be interconnected for forming a still larger communications system.

As a further aside, it is well known that electrical signals, depending upon the electromagnetic transmission characteristics of the transmission medium, typically propagate on a communications channel at a speed in the range 0.6 to 0.9 of the speed of light, which is estimated here to be about 186,000 miles per second. For ease of discussion, the estimated speed of light is here translated to an electromagnetic propagation speed of approximately one foot per nanosecond. Accordingly, it should be clear that channel 10 may be busy at one station, e.g., at station 30-i, only while a packet is electrically being received at, or transmitted from, the station; otherwise channel 10 is not busy, or iε idle, at least as to station 30-i. Thus, channel 10 can be busy as to one station and not busy (or idle) as to another station.

_ OMPI

[AL> WIPO SNATI

Before more particularly describing the invention, some lexicon is further clarified.

Signals in a communications system may be categorized according to many, sometimes varied, criteria. One way of categorizing signalε iε as between signals of a first kind, which may be typified by, but not limited to, digitized analog speech signalε, and εignals of a second kind, which may be typified by, but not limited to, digital computer signals. Here, signals of the first kind are aεεumed to have some periodic or quasi-periodic characteriεtic while εignalε of the εecond kind are aεεumed to have εome nonperiodic or aperiodic characteriεtic. For brevity of diεcuεεion and not by way of limitation upon the inεtant invention, the firεt kind of signals are hereinafter usually referred to by words such as "voice εignalε" or "εpeech εignalε" or "periodic signals". Accordingly, such signalε are transmitted from, or received at, a "periodic source". As an example, it is common to generate such signalε by εampling speech signals at a 8,000 hertz rate and converting each analog sample to an eight bit digitized voice sample.

On the other hand, the second kind of signalε are hereinafter usually referred to by such wordε aε "data signalε" or "aperiodic εignalε". Accordingly, εuch εignalε are tranεmitted from, or received at, an "aperiodic source".

It should also be borne in mind that a source can be both a periodic source and an aperiodic source and that the adjective applied to a source iε only an indication of the function of the εource at that inεtant in time.

DIGITAL VOICE VERSUS DIGITAL DATA In a communicationε εyεte , tranεmiεεion needs, in terms of capacity and in terms of delay, are usually different for digital voice signals (e.g., digitized analog speech) than for digital data signalε, (e.g., digital computer-to-computer) . ^tiϊ E iT

For example, digital voice traffic such as may be related to digitized telephone calls commonly involves transmitting a large number of bits. Using a thirty-two kilobit per second speech coder and transmitting only during active speech intervals, over four and a half megabits of digital voice traffic would be transmitted during a typical three minute telephone call. Also, digital voice traffic commonly involves relatively stringent delay requirements. For example, whereas the maximum delay allowed during a typical telephone call is in the order of a few hundred milliseconds, in a local network, the maximum delay could be expected to be significantly less than a few hundred milliseconds. Accordingly and because the participants (such as the calling and called parties) usually interact, it may be unacceptable for digital voice traffic to be accumulated over the entire time interval of the call and then to be transmitted as a large digital file transfer. Further, in a voice packet system, overhead bits can be transmitted in addition to the information bits, the latter representing the digitized voice samples. Hence, the more voice samples included in a packet, the higher the ratio of information bits to total bits and the higher the transmission efficiency of the channel. However, the more voice sampleε included in a packet, the greater the delay between the time a sample is generated and the time it is delivered to, for example, the receiving telephone. Accordingly, as a compromise in the balancing of the aforecited interests, voice packets including several tens of milliseconds of speech are asεumed in the instant illustrative embodiment. Also, for example, digital data traffic commonly involves a statistical distribution which is typically bimodal and which comprises short interactive messages as well as large file transferε. Commonly, traffic from digital data εources arrives sporadically, or aperiodically, at the channel. Thus, if a message is divided into data packets, a statistical variance in packet

OMPI i^ , WIPO

delay can usually be tolerated, providing the entire message delay is not exceεεive.

As to a discontinuity problem, the variance of the delay in a voice packet system could also be constrained to solve the following problem. A digital-to- analog converter, typically at a receiver, converts the digitized voice εampleε at a fixed rate for reconεtructing the analog εpeech wavefor ε. If a packet of samples is delayed to the extent that previously transmitted sampleε are completely converted before the delayed packet arrives, the receiving listener would usually perceive a discontinuity in the speech. To solve that problem, if the maximum packet delay iε conεtrained, the probability of the aforedescribed problem occurring can be reduced. Accordingly, the packet delay can be constrained by a technique in which the first packet of voice samples, which arrives at the receiver, is delayed and thereafter later packets are buffered until the later packets are needed. The delay of the first packet adds to the overall delay between the speaker and the listener and would normally be kept εmall. Alternatively, if the maximum delay iε not conεtrained, the deεcribed technique could reduce, but not necesεarily eliminate, the discontinuity problem.

As to a diεtortion problem, on the one hand, packetε of voice εampleε that do not arrive in time at the deεtination, e.g., the delay requirements are not met, can normally be discarded. It can be argued that, if a small percentage of voice packetε are diεcarded, the reεultant diεtortion is tolerable. On the other hand, experimentation indicateε that voice packetε are generated in a generally periodical manner. Hence, if packetε from voice sources were to collide, they would likely continue to collide on succeεεive tranεmiεεions. Therefore, succeεsive delays from the same voice source would tend to be correlated. Voice sources that do not contend with other voice sources for access to the channel may have a εmall average delay and a εmall variance of delay, while

OMPI . WIPO

those that do contend with other voice sources may have a large average delay and a large variance of delay. If systems and networks are designed based upon an acceptable average level of "lost" (e.g., discarded) packets and the lost packets are concentrated among a small number of connections during a small period of time, rather than being distributed randomly, the resultant distortion may not be tolerable.

According to an aspect of the instant invention, instead of reducing the periodicities to achieve a reasonable level of lost packets, voice sample periodicitieε can be used to eliminate loεt packetε entirely. This is accomplished by the about to be described, variation on a carrier senεe multiple acceεs/collision detection (CSMA/CD) transmission protocol or method.

The instant method contemplates transmitting data packets by conventional CSMA/CD techniques such as are discloεed in the aforecited U. S. Patent 4,063,220, but also contemplates transmitting voice packets by a new and different technique. Generally, according to the method, periodic sources do not detect collisions. In addition, periodic voice packets are formatted, as is later described, to mitigate the deleterious effects of a collision. Further, periodic voice packets are given a higher retransmisεion priority than are aperiodic data packetε. Finally, the length of aperiodic data packetε is constrained.

Advantageously, the instant method limits the delay of voice packets to the time for transmitting one data packet, which time, aε will shortly be made more clear, does not exceed the time for transmitting one voice packet. Also advantageously, the instant method avoids collisionε with a voice packet. As a result of employing the principles of the instant invention, periodic sources using the instant protocol appear to operate on a channel as if a time slot

OMPI

of a time division multiplexed (TDM) signal had been asεigned to each respective voice source. A difference between the instant channel and a standard TDM channel is that a station on the instant channel is not locked εolidly into a time εlot. Indeed, the time εlot may be εhifted slightly backward in time. While the backward shift occurs, as will hereinafter be described, voice samples that arrive during the shift are tranε itted in an expanded packet data field, called an overflow field. Another intereεting advantage of the inεtant protocol iε that a periodic source can gain accesε to a εyεtem even though the protocol appearε to be unable to handle the additional capacity. The εyεtem doeε not fail, but tendε to operate aε a fully utilized TDM εystem, albeit with a εlightly longer time εlot.

Still another advantage of the inεtant protocol iε that, with the time εlot mobility, timing diεcrepancieε can exiεt between periodic sources without time slotε being overwritten, which further obviates collisionε with a voice packet.

PACKET FORMATS In preparation of describing more specifically the instant control protocol, FIG. 2 depicts the format of a well known, yet illustrative, aperiodic packet for communicating data traffic. For illustration, the data packet is asεumed to include a plurality of fieldε, each field including one or more bitε. Here, a data traffic packet may compriεe two fieldε. For example, the packet may comprise an overhead field of H _A bits and a data field of I _A bitε. Aε is common in the art, the overhead field may, in turn, include a preamble field for timing and synchronizing, a destination εtation addreεs field for identifying a called station, a source station address field for identifying a calling station, a packet length field for identifying the number of information bitε, a packet εequence number field for identifying where the

OMPI

packet fits in a mesεage having a plurality of packetε, an error control field for checking errorε in the packet, and perhaps other field (s) for identifying other attribute (s) . The data field is for inserting the "aperiodic information" to be transmitted, here shown as including a variable number I _A of bits.

FIG. 3 depicts a format of an illustrative periodic packet for communicating voice traffic. In accord with the principles of the inεtant invention, and yet for purpoεes of illustration, the voice packet is also asεumed to include a plurality of fields, each field also including one or more bits. Here, a voice traffic packet may comprise four fields. For example, the periodic packet may comprise a preempt field of P _p bits, an overhead field of H P bits, a data field of I_ ir. bits, and an overflow field of

0 bits.

During the time interval of a preempt field, a periodic source would place a signal on the transmiεεion media but would not εend "uεeful information". The preempt interval would be, timewise, long enough for a transmitting aperiodic station source to detect a collision, stop transmitting its packet, and have the effects of the transmission removed from the system before the periodic source begins transmitting "useful information". The estimated time length of the preempt interval, τ _p , is approximately: p t on I off where τ _t is the one way propagation delay in the medium, τ. _Qn is the time required for the signal level to become detectable, t - is the time for an interfering signal to be detected, and τ _off is time for a signal that is turned off to stop effecting a receiver. By way of example, the bit length of the preempt field in a three megabit per second, one kilometer channel εystem could be (P _p =) 38 bits long. The length of an overhead field for a periodic packet will typically be less than the length of an overhead field for an aperiodic packet. For example, the

OMPI ^ 1PO

overhead field of an aperiodic packet may be (H _A =)100 bits while the overhead field of a periodic packet may be (H =)48 bits. Reasons for the smaller periodic packet overhead field include the following: (1) Since retransmitted packets can uεually be expected to arrive too late to be uεeful, an error control field iε not necessary for periodic sources. Alεo, it iε known that a greater error rate can be tolerated in εampled voice traffic than can be tolerated with data traffic,

(2) Since periodic packets do not arrive out of sequence, a εequence number field is not necessary, and

(3) Since periodic packets are asεumed to be fixed or determiniεtic in length, a packet length field iε not neceεεary. Aε to the data field, when a periodic εource acquireε access to the channel, it transmitε in the data field all the data that has accumulated since a last transmiεsion. The source schedules its next packet transmiεεion to occur a predetermined time T _p εecondε after the εucceεεful tranεmiεεion of the current packet. If the channel iε not buεy (i.e., iε idle) at the end of the T εeconds, voice samples accumulated between transmisεions will be inserted into the data field and then transmitted as a periodic packet. If the channel is busy at the end of the T seconds, the station waits for an channel (WIC) before transmitting the periodic packet. Samples that arrive during the (busy) waiting time can be inserted in the overflow field of the periodic packet and transmitted when the channel becomes idle. The size of the overflow field is determinable as a function of the maximum delay a

OMP

^ VIP

periodic source can experience. According to the instant method or protocol, the maximum delay for a periodic source fortuitously will not exceed the time for one aperiodic packet transmiεεion. In one system, where a periodic source may generate 8000 samples per second and where each sample may comprise four bits and where T _p is 30 milliseconds, a maximum of four sampleε could arrive during a packet transmission interval. Therefore, in that system, the overflow field comprises (0 _p =)16 bits. On the other hand, even when there are no overflow samples to be transmitted, the source can transmit a "don't care" condition, e.g., εignal carrier, during the overflow time. Advantageously a periodic εource takeε no more time to transmit a packet when it is delayed, e.g., because the channel is busy, than it takes when it acquires access to the channel immediately.

Aε priorly mentioned, it may be noted that the firεt packet from a periodic εource may be εhorter than εubεequent packetε εince the firεt packet need not include either a preempt field or an overhead field. However, it may alεo be noted that the same packet size could be maintained for the first packet as for all other periodic packets. This makes consiεtent the reεult that the scheduled time interval between the next packet from one source and a packet from another periodic source is at least one periodic packet transmission time, X _p seconds.

THE TRANSMISSION PROTOCOL Now and referring to FIG. 4, the instant method or protocol is even more specifically described. At the same time, it should be clear that the instant protocol may be embodied in hardware or in software at each of stations 30-1 through 30-N of FIG. 1 using well-known techniques when taken in conjunction with the instant description. With the instant protocol, if a periodic source and an aperiodic source are waiting to use a busy channel.

MPI

the periodic source is assumed to have a higher access priority and hence acquires the channel first. Also, on the one hand, all of the packets from an aperiodic source and, perhaps, the first packet from a periodic source can use aspects of a conventional carrier sense multiple access/collision detection (CSMA/CD) protocol. On the other hand, a packet from a periodic source can use aspects of the instant protocol.

More particularly, before starting to transmit, the source, whether periodic or aperiodic, listenε to the channel (LBT) , refrainε from tranεmitting if the channel iε buεy (B) and waitε for an idle channel (WIC). If the channel is not buεy (B) , the εource, whether periodic or aperiodic, beginε to transmit. While transmitting, a periodic source does not listen to the channel (TLWT=N0) , rather it transmits (XMIT) , in a fixed length packet, all of the voice samples that it has accumulated since its last transmission. The periodic source then schedules its next transmission to occur at a fixed time T _p secondε after itε laεt εucceεεful tranεmiεεion. For brevity only, in the inεtant illuεtrative embodiment, it iε aεεumed that T _p iε the εame for all εourceε.

Alternatively, an aperiodic εource listens to the channel (TLWT=YES) and, if a collision (C) with another source is detected, the source stopε tranεmitting and thereafter waitε for an idle channel (WIC); elεe, if no colliεion (C) iε detected, the source continueε to transmit. Accordingly, if the channel is buεy (B) for either periodic or aperiodic source or if a collision (C) occurs for an aperiodic εource, the reεpective εource waits for an idle channel (WIC) and reεchedules a transmiεεion, i.e., trieε again after the channel becomeε idle (SRB or SRC) . From the foregoing and in accord with an aεpect of the instant invention, a periodic source listens before transmitting (LBT) and defers transmiεεion priority to any

OMPI

terminal that iε then transmitting. Then, when an idle channel is detected, the periodic εource begins transmitting. However, the periodic source does not listen (TLWT=N0) while transmitting but rather continues to transmit (XMIT) the entire periodic packet and does not terminate transmission prematurely. Notwithstanding, the instant protocol prevents packets from periodic sourceε from colliding. This fortuitous result obtains, in part, because there is a constraint on the packet size from aperiodic sources. Also, respecting a collision between periodic and aperiodic sourceε, the FIG. 3 packet structure for a periodic source is designed to allow an aperiodic source to detect a collision and terminate the aperiodic transmission during the preempt interval and before the periodic source begins transmitting "useful information", the useful information including, for example, the overhead field, the data field, and the overflow field of the voice packet.

As to εtill another advantage, as greater amounts of periodic traffic enter the system and because of a fixed length periodic packet, the εystem tends to resemble a time division multiplexed system. For example, a periodic source may acquire the channel and periodically use a "time slot" until either aperiodic traffic prevents accesε to the εlot or another periodic εource εtartε to tranεmit. In either event, and at that point in time, the periodic εlot, which had been εcheduled for the next periodic εource, is shifted slightly backward in time. Additional data can be transmitted in the first delayed slot to compensate for the time shift.

Thus in summary, as to the rules for accessing the channel, it may be said that with the instant method:

(A) ACCESSING RULES FOR APERIODIC DATA TRAFFIC

The data traffic access rules are similar to those used in conventional random accesε broadcast networks

The aperiodic acceεε ruleε include:

(i) Liεten before tranεmitting (LBT)

Before εtarting to transmit, liεten to the channel. If the channel iε buεy, someone elεe is transmitting, accordingly, do not transmit. If the channel is not busy, also called "idle" herein, then transmit.

(ii) Listen while transmitting (LWT)

While transmitting (TLWT=YES), listen to signals on the channel. If the data become distorted, indicating that someone else is also transmitting, i.e., a collision, stop transmitting; otherwise, continue to transmit.

(iii) Retry strategy

If the channel is buεy or if a colliεion occurs, wait for the channel to become idle, then schedule the next transmission attempt according to any of the standard (e.g., random) retry ruleε.

(B) ACCESSING RULES FOR PERIODIC VOICE TRAFFIC

The voice accesε ruleε take into account the periodicity of the voice traffic. The ruleε are different from any known method. The ruleε eεtabliεh an upper limit on the delay experienced by voice packetε. The improved periodic access rules include:

(i) Listen before transmitting (LBT)

Before starting to transmit, listen to the channel. If the channel is busy, someone else iε transmitting, accordingly, do not transmit. If the channel iε not busy, then transmit.

(ii) Do Not Listen while transmitting

While transmitting (TLWT=N0) , do not liεten to signals on the channel.

Rather, continue to tranεmit the entire periodic packet before releasing accesε to the channel. A preempt field will be used to alert and, responsive to which, permit any aperiodic data source which may collide with the intended periodic packet transmission to be turnedoff. Advantageously, voice packets will not collide.

(iϋ) Retry Strategy

If the channel is busy, εchedule the next transmission attempt as an immediate retry.

(iv) Transmission

Transmit, in the data field of the periodic packet, all voice samples which arrive within T _p secondε of a laεt transmisεion. Before releasing access to the channel, transmit, in the overflow field of the packet, all samples which

OMPI

arrive during the time a periodic packet is delayed.

(v) Scheduling Next Packet

Schedule transmiεsion of the next packet a predetermined time T secondε after tr the laεt εuccessful periodic packet tranεmisεion.

(C) ALTERNATIVE ACCESSING RULES FOR A FIRST VOICE PACKET

The firεt packet in a voice tranεmiεεion can have the εame length aε a normal voice packet, but follows the accesε ruleε of a data packet.

DELAY CONSIDERATIONS Delay can be encountered in a network when a channel iε busy such that concurrently transmitted packets could or do collide. For example, a periodic εource can be delayed when:

(1) The channel iε buεy tranεmitting an aperiodic packet;

(2) A collision with an aperiodic source occurs;

(3) The channel iε buεy tranεmitting a periodic packet; or

(4) A collision with a periodic source occurε. In accord with the principleε of the inεtant invention, only the firεt and third of theεe four conditions delay a periodic source. This obtains because, referring to FIG. 4, both an aperiodic εource and a periodic εource liεten to the channel before tranεmitting (LBT) and,

OMPI IPO

responsive to a busy channel, the source waits for an idle channel (WIC). Further, the maximum delay experienced by a periodic source does not exceed X _p where X _p equals the time to transmit a periodic packet. Here, it is assumed that each and every periodic source has the same minimum intertransmission delay time T . The effect of timing inaccuracies is described hereinafter.

As to the εecond of the four delay conditions, firstly, when a periodic source and an aperiodic source collide, the aperiodic source detects the collision during the preempt interval of a packet from the periodic source and stops transmitting before the periodic source beginε transmitting uεeful information. Therefore, a periodic εource is not delayed by a collision with an aperiodic source.

Also as to the second delay condition, secondly, when a periodic source and an aperiodic source are waiting for an idle channel, the periodic source wins the race and gains access to the channel. This result obtains becauεe the periodic εource beginε transmitting upon detecting the channel as idle. If the aperiodic source waits, it detects a busy channel and does not transmit. If an aperiodic source does not wait but rather begins transmitting, it detects a collision during the preempt interval of the periodic source packet and stops transmitting. Therefore, a periodic source can only be delayed by either a periodic source or an aperiodic source whose tranεmission is already in progress. This delay is at most one periodic packet transmisεion time. As to the fourth delay condition, consider a plurality of k periodic packet sources. Now consider a first εequence of intended transmiεsions from the respective periodic sources on a channel, the sequence being defined so that a packet from source 30-i is scheduled for transmission before a packet from source 30- (i+1). Let

(a) t _j represent the time that a

OMPI

^&?NATlθ5

transmiεεion from source 30-i iε scheduled to be received at destination 30-j. Hence, times tj 2. r ^fc 2 2'"* ^,t k k ^{are a} ^- ^so approx ^¬ imately the times the reεpective k sources are scheduled to transmit a packet

(i.e., intraεtation tranεmiεεion time iε asεumed to be negligible), i

(b) t.- r.Jϊ repreεent the time that a tranεmisεion from source 30-i actually is received at source 30-j, and

(c) D_. r j• = t,- J; ^■ r J - t-,- J. "- fj represent the delay a packet encounterε in being tranεmitted from εource 30-i to deεtination (εource) 30-j. . Now aεεume that the transmisεion from each periodic εource laεts a time X _p seconds. That is, the packet transmiεεion time required by a periodic source 30-i to transmit a fixed-length packet is X _p even though the packet is delayed and even though the packet may include waiting time voice samples in its overflow field.

Therefore, as between one periodic source 30-i and another periodic source such as source 30-(i+l),

ti+lji+l ^{" t} i,i+l 2. ^x p ^(χ)

which may also be written as

^+1,1+1 >. ^fc i,i+l ^{+ X} p < ² >

Since media propagation time is usually independent of the delay, the delay is the εame for each εource. Hence, the notation D,- ^ = D.- iε used hereinafter.

Now, if D^ equals zero, periodic source 30-i does not delay another periodic source such as source 30-(i+l).

Further, as long as D^ does not exceed X _p , the two periodic sources, i.e., sources 30-i and 30-(i+l), will not collide.

Alεo, it may be noted that a periodic εource cannot be delayed by another periodic source which has not itself been delayed. Therefore, if a periodic εource iε delayed by another periodic source, the other periodic source must have been priorly delayed. Accordingly, the delay incurred by the first periodic source to be delayed does not exceed X .

In light of the above, a packet from periodic source 30-(i+l) is not delayed by periodic εource 30-i. On the other hand, the (i+l)th periodic εource may be delayed by an aperiodic εource, reεponεive to which, a εecond εequence of intended but delayed tranεmissionε from the reεpective periodic sources may be considered. Notwithstanding, the delay which εource 30-(i+l) incurε will not exceed X _p and the periodic sources will not collide. This delay may propagate and effect a sequence of periodic sourceε. For example, in a general εequence of periodic εourceε, if

then.

^t i,i+l ^{< t} i+l,i+l'

and, the i ^th and (i+l) ^th εources do not collide. Further, the transmission time required by the i periodic source is X , even though it is delayed, and muεt tranεmit more samples. If,

^t i,i+l ^{+ X} p i ^t i+l,i+l'

then, the (i+l) ^th εource is not delayed by the i ^th periodic source. This source may be delayed by an aperiodic source, and start a new sequence of delayed εourceε, but the delay it incurε will be less than X _p . If,

^fc i,i+l ^{+ x} p ^fc i+l,i+l'

the delay encountered by a packet being tranεmitted from the (i+1) th εource iε t Di.+1 = t.,ι.+,l _n - tι.+.l..,ι.+_,l.. + Xp. (3)

Since the (i+1) th periodic source is waiting for the channel, the delay cannot be increaεed by an aperiodic εource. This is so because a periodic source has priority over an aperiodic source, which priority is embodied through the preempt field. The delay D _i+1 can be written as

^D i+1 = ^D i + ^fc i,i+l " ti+1,1+1 ⁺ < >

Since, by rewriting equation (1) to a form

ti,i+l " ti+l,i+l + ^x p < ° ⁽ 5 ⁾

it is clear that D^ ₊₁ does not exceed D^. Therefore, the delay incurred by a sequence of periodic sourceε iε a non- increasing function, and the maximum delay incurred by a periodic εource does not exceed X _p , and periodic sources do not collide.

Thus in εummary, aε to voice packet colliεions, it may be said, with the instant protocol, that:

(A) As to a voice packet collision with a data packet

(i) If a data packet accesses an idle channel, and its signal arriveε at a voice εtation before the voice εtation starts transmitting, the voice station may be delayed from transmitting for at most one aperiodic data packet transmiεεion time.

OMPI

(ii) Aεsu e a data εtation and a voice station begin transmitting at approximately the same time. A collision would occur in a conventional system. With the instant method, the data source detects the voice packet and removes the data packet from the channel before the pre-empt interval of the voice packet is complete. Therefore, the useful voice information is not distorted, and the voice packet is not delayed.

(iii) Aεsume both a data packet and a voice packet are waiting for a busy channel to become idle. After the channel becomes idle the voice source immediately begins transmitting while the data source starts transmitting some (perhaps random) time later, Even if the data packet begins transmission before it detects the voice packet, it will be turned off during the pre-empt interval.

(iv) The result of the foregoing iε that a voice packet can be delayed by at most one aperiodic packet time interval.

(B) As to a voice packet collision with a voice packet

(i) The next transmiεsion from a voice source is scheduled T secondε after the channel iε εucceεεfully accessed. Since two stations cannot succesεfully accesε the channel at the same time, their next transmisεionε will not interfere unless one of them

_ OMPI

^ WIPO

iε delayed .

(ii) If the preceding voice source iε delayed by a data source, the delay will not exceed one aperiodic packet transmiεεion time. Voice εampleε accumulated during the delay will be transmitted in an overflow field, which is transmitted, i.e., whether or not there is a delay. Therefore, the voice source will not be delayed by more than one aperiodic packet transmiεεion time, and will not delay future voice εourceε by more than one aperiodic packet tranεmission time.

(iii) The minimum spacing between voice packets is a voice packet transmission time X _p . The maximum delay cauεed by a data packet colliεion is one data packet tranεmiεεion time. The data packet tranεmission time does not exceed a voice packet transmiεsion time. Therefore, there will never be two voice packets waiting to acquire a busy channel, and two voice packets will not collide.

(iv) The maximum voice packet delay is one data packet transmiεεion time. Thiε determineε the overflow field εize, i.e., the number of bitε needed to tranεmit voice εamples which arrive during a data packet transmisεion time.

OVERFLOW TRAFFIC Consider a system operating in a mode in which the channel capacity is almost completely used by periodic sources. Asεume that a time gap remains between scheduled transmissions which gap is large enough for another source to begin transmitting but which gap is not large enough to transmit an entire periodic packet. Assume that another periodic source has accesε to the channel at thiε time. In εuch a εituation, the εystem begins to operate without time gaps. The period of time between channel acquisitions increases, and some or all of the bits in the overflow field in every periodic packet are used. However, whenever a periodic source can acquire the channel, it can transmit its packet. For example, let a periodic source begin transmitting in a small time gap. The periodic source, which is delayed, is delayed for a time that does not exceed X . The source will transmit in its overflow field all voice samples accumulated during the delay. The source also scheduleε itε next transmission to begin T _p seconds after it succesεfully completed its last transmission.

Successive periodic sourceε are delayed by a time interval which iε leεε than or equal to the time delay incurred by the preceding source. The original interfering source becomes another εource in the εequence of interfering εourceε. It can be delayed by no more than the delay it originally cauεed and can delay the εource following it by no more than it did originally. Since the delay iε a non- increasing function and since it cannot go to zero for the over-utilized channel, it must stabilize at some positive time, _ε , which is the same for all sources. The delay, ε, is equal to X _p minus the sum of the idle channel times for a period T_ before the overflow source entered the channel.

When the stable situation occurs, each periodic source transmitε a packet every T _p + ε εecondε. It tranεmitε the samples which have arrived in this interval of time in the data and overflow fields of the transmitted packet. At the end of each transmiεsion there would be a

OMPI WIPO

periodic source which has been waiting _ε secondε. The waiting εource acquireε the channel before an aperiodic εource aε well as before the firεt packet from another periodic source. Until one of the εourceε terminateε itε tranεmiεsion, at which point in time channel capacity becomes available, the system operates as a time division multiplexed syεtem with a "time εlot" period of T _p + ε εecondε. No data iε loεt, and the εlot delays do not grow indefinitely.

TIMING CONSIDERATIONS

In a sampled communications system, it is common for the transmitter and receiver to be frequency synchronized εo that εampleε are tranεmitted at the εame rate at which they are generated. In broadcaεt networkε, the synchronization can be achieved by sending a clock εignal outεide of the normal εignal band or alternatively by uεing a modulation rule with a clock component. The former technique provideε accurate timing, but requires that one station be reεponεible for εending the clock signal on the syεtem. In the latter technique, there is no centralized control and every tranεmitting εtation iε identical, but timing diεcrepancieε may exiεt between the transmitters, particularly when very little data is being transmitted. Timing discrepancieε reεult in the periodic εtationε having different estimates of the interpacket interval T^ _p . For example, assume that the interpacket interval T^ _p for periodic source 30-i is within ε secondε of T , εo that: T _j _ - T_ < _ε . Let periodic εourceε 30-i and 30-(i+1) tranεmit at timeε t^ ^ ₊ _ - t and t + X _p , reεpectively, εo that there iε no εeparation of the packetε at εource 30-(i+1). The next packetε from these sourceε are scheduled at times

^,1+1 = ^t+T i,p ^and ^+1,1+1 = ^{t + x} p ^+τ i+l,p respectively. These two latter times may be separated by as little as

Xp - 2ε. If the firεt packet in thiε εequence iε delayed

OMPI IPO

by a packet from an aperiodic source, it may be delayed until t _{j i+1} < t + _j + X _a . With the constraint X _Q X _p , it is possible that both periodic sources will be waiting for the channel and collide. Such a collision can be prevented by constraining the length of an aperiodic packet to: Xa_ —< Xp_ - 2ε . With this constraint, the seq ^J uences of periodic sources do not collide, and the delay of an aperiodic source X _a is less than X _p .

OMPI ?NAT1Q