Note: Descriptions are shown in the official language in which they were submitted.
CA 02242985 1998-07-14
CA9 98 023
A Method of Adding Quality of Service Capabilities to
CSMA-CA Based Protocols for the Purpose of Isochronous
Communication and Coexistence of Multiple Physical Layer
Modulation Schemes
Field of the Invention
This invention relates to the field of networking using Medium Access Control
(MAC),
and more particularly slotted Carrier Sense Multiple Access (CSMA) protocol,
also
called CSMA-CA (Collision Avoidance) protocol, and also to networks that use
carrier
modulation
Background
To address some problems of the prior art, the utility of the invention is in
the field of
guaranteed Quality of Service (QOS) parameters, with specific attention to
guaranteed
latency and bandwidth (also known as isochronous) parameters and in case of
wireless
networks deals with hidden node issues.
Brief Description of the Drawings
Figure 1 shows the International Standards Organization's (ISO) conceptual
reference
model of a network device, called the Open Systems Interconnection (OSI)
reference
model;
Figure 2 illustrates 2 overlapping wireless networks;
Figure 3 illustrates the block level architecture of the embodiment of the
coexistence
and interpretation of multiple physical layer modulations.
The conceptual model of a network can be represented in the OSI reference
model
which is depicted in Figure 1 in which it can be seen that a network can be
considered
as a layered structure, including an Application Layer 1, Presentation Layer
2, Session
Layer 3, Transport Layer 4, Network Layer 5, Data Link Layer 6, MAC Sublayer
7, and
CA 02242985 1998-07-14
CA9 98 023
Physical Layer 8. This model of a network is well known in the art and can be
referred
to during a review of the description below.
In a typical CSMA based network each device or station in the network is
required to
carrier sense the medium (detect the presence of a physical carrier generated
in the
medium generated by a station transmitting information in the medium) before
it begins
to transmit. The amount of time required to detect the presence of a carrier
is
dependent upon the modulation method of the electronic design of the
underlying
physical implementation of devices in the network.
If a station using a CSMA MAC protocol detects a carrier (generated by another
CSMA
MAC station) the particular CSMA MAC protocol followed will do one of two
things;
persistent type carrier sensing CSMA MAC stations will continuously monitor
the carrier
signal from a station that wants to transmit and transmit as soon as the
carrier
disappears; non-persistent type CSMA MAC station will wait a finite period of
time and
carrier sense once again. If a carrier is present then the process is
repeated. To avoid
collision that would occur if 2 or more MACs were presented with data to
transmit at the
same time when following a persistent CSMA MAC protocol, a station may or may
not
transmit when no carrier signal is detected. Such CSMA MAC protocols are
referred to
as CSMA MAC protocols with collision avoidance, CSMA-CA MAC protocols. The
decision to transmit is based on a protocol dependent probability of
transmitting. If the
probability is very high (closer to 100%) then the device is more likely to
transmit when
an idle channel is detected that a device with a lower probability of
transmitting.
Another concept that can be applied to CSMA MAC protocols is that of slotting.
If
certain actions followed by the CSMA MAC protocol can only occur after certain
fixed
periods of time the CSMA MAC is referred to as a slotted CSMA MAC. For example
if
interval of time between carrier sensing the medium in (non-persisten) CSMA
MAC
protocols or CSMA-CA MAC protocols is made up of multiple fixed duration time
periods (referred to as slots), then these CSMA protocols would be referred to
as
slotted CSMA or slotted CSMA-CA MAC protocols.
CA 02242985 1998-07-14
CA9 98 023 3
Regardless of the nature of the CSMA MAC protocol, it is possible that 2 or
more
stations in the network will eventually attempt to transmit their data at the
same time. If
the devices do not detect the collision, the bandwidth of the medium consumed
during
the combined transmissions is wasted. If the devices are able to detect the
collision
then the amount of bandwidth wasted due to the collision is limited to the
amount of
time required for the devices to detect the collision. This further
enhancement, collision
detection, is employed by CSMA-CD (Collision Detection) MAC protocols.
The referenced prior art CSMA MAC protocols share a basic common problem. It
is
extremely difficult to determine how long it will take a station using these
CSMA MAC
protocols to transmit a given block of data. The amount of time to transmit a
given
block of data depends on at least 2 factors: the time required to access the
channel and
the time to place the data on a channel. The amount of time required to place
the data
on the channel is deterministic and can easily be calculated by those skilled
in the art
based on the size of the data block, the base baud rate (measured in bits per
second)
of the channel and the modulation employed in encoding the data on the
channel. The
other component, channel access time, is dependent upon the number of other
devices
simultaneously contending for the channel, the amount of data these devices
place on
the channel, and the nature of the particular CSMA MAC protocol being
employed.
These dynamic parameters of the second component are simply unknown to a
device
that is attempting to gain access to the channel. Thus the channel access
time, or
transmit latency time, may be statistically bound, but is not deterministic.
Therefore, in prior art CSMA networks it is virtually impossible to guarantee
the amount
of time required to transmit a given block of data. But this parameter is
fundamental in
providing a known quality of service for isochronous communications over a
link
between stations in the network.
The specific QOS parameters that are sought to be supported are:
1) A time-to-live parameter associated with a given block of data (the
maximum amount of time that the data is considered valid)
CA 02242985 1998-07-14
CA9 98 023 4
2) A guaranteed latency time for data transmission
3) A guaranteed bandwidth.
The time-to-live QOS parameter ensures that if the MAC is unable to begin
transmitting
a given block of data within a given period of time that the MAC will simply
discard the
data instead of exceeding the time-to-live parameter and transmitting the
data. This is
useful when the data arrives periodically and is invalidated by the next
periodic update.
If the given data block can not be sent before the next periodic update of the
information, then there is no value in having the MAC consume network
bandwidth for
the purpose of transmitting stale data.
The guaranteed latency QOS parameter ensures that the MAC will be able to send
the
given block of data on the network within the latency interval specified. The
MAC
determines what range of latencies is supportable and must fail any request to
provide
guaranteed latency with too small a latency parameter.
Finally, the guaranteed bandwidth QOS of service ensures that a network layer
above
the MAC will have access to the medium for some guaranteed interval of time
during
which it will always be able to transmit a precise amount of data. Therefore,
by dividing
the maximum amount of data that can be transferred by the guaranteed access
period
gives the guaranteed bandwidth parameter.
The hidden node problem arises as a result of the limited range of wireless
devices.
Two devices out of range of each other may simultaneously attempt to
communicate
with a device in range of both of them thus causing interference hampering
successful
communications.
Communication networks are made up of the following components, a medium,
signal,
a modulation technique, a physical layer and a data link layer that may or may
not
contain a Medium Access Control (MAC) sublayer and higher network layers. A
medium is a physical or spatial entity that is able to transfer one or more
signals. A
CA 02242985 1998-07-14
CA9 98 023 5
signal is a recognizable pattern that in the context of this invention refers
to a single
carrier. A modulation scheme is a method of encoding information into the
signals)
that the medium is able to transfer. A network physical layer translates data,
in the
form of packets, from upper network layers into modulated information carrying
signals
that can be efficiently transferred across the medium. The physical layer must
be able
to submit modulated information to the medium and be able to extract the
modulated
information from the medium. In computer networks this involves the
translation of data
bits into the modulated signals sent over the medium. For efficient network
performance, the MAC needs to coordinate the physical layer's activities to
ensure that
multiple physical layers do not attempt to simultaneously submit signals onto
the
medium if that process will cause interference rendering each signal
unintelligible to
other physical layer entities. In networks where there are only 2 valid
signals, the
common carrier and silence, this is essential.
The decision to only employ a single carrier wave allows for a simple, cost
efficient
implementation of the network physical layer hardware. Since the carrier is
switched on
and off as a result of a particular pulse modulation technique, such networks
are only
able to transfer a serial stream of binary (on/ off) information. Therefore
such networks
are ideally suited to the serial transmission of binary data from a computing
device.
The method of mapping binary information to the presence or absence of the
common
carrier is determined by the particular pulse modulation technique employed.
The
simplest technique would encode a binary 1 as a pulse, and a binary 0 as
silence.
Under such a modulation scheme, the maximum baud rate that could be supported
over the medium depends on how fast the hardware used to generate the pulses
is
clocked. This is a complex decision that is dependent upon many factors,
power, heat,
the time required for a receiver to lock on to the carrier and regenerate a
binary pulse,
cost and others. As technology advances, it may be possible to increase the
clock rate
of the pulse stream, or more efficient methods may be found to encode the
binary data
stream. These effects will result in different modulation techniques that can
be applied
to the common carrier. If the carrier frequency is much higher than the
marginal
improvements in the data rate brought about by better modulation methods, then
the
CA 02242985 1998-07-14
CA9 98 023 6
common carrier itself will not need to change as often as the modulation
techniques.
This means that enhancements in the modulation methods employed in these
networks
require changes in physical layer hardware but not necessarily the medium
through
which the common carrier is sent. This is obviously the case in wireless
networks.
Modulation enhancements are also commonly followed by new physical layer and
MAC
layer protocols to take advantage of those enhancements. The end result is a
collection of hardware components that share a common carrier signal that
employ
different modulation techniques using different physical and MAC layer
protocols. This
means it is impossible for devices listening for and modulating the common
carrier to
inter-operate. Even worse, the different networks must employ different
mediums or
else they will interfere with one another since they all share a common
carrier. For
mediums that require physical conduits through which to transmit the common
carrier,
the problem is easy to resolve: Simply ensure that the different networks
employ
different physical conduits to transfer the common carrier.
However, in wireless networks the problem is harder to resolve since the
medium is
typically free space. Therefore if devices employing different modulations of
the same
carrier are in range of one another the interference problem can not be
resolved.
Devices belonging to the different networks must be spatially separated or
temporally
separated. Either solution will solve the interference problem but do not
address the
interoperability problem.
Both inventions mention concepts employed in Time Division Multiplexing (TDM)
and
Time Division Multiple Access (TDMA) networks. TDM is the process in which
entities
are given access to a shared resource in a simple round robin fashion. In
reference to
networks, TDMA networks employ the concept of TDM to allow stations a period
of time
in which they are exclusively permitted to send data in the medium in round
robin order.
One of the problems in basic TDMA networks is that medium bandwidth is often
wasted. This occurs as a result of each station usually being allotted the
same fixed
period of time in which to transfer their data. If the station does not have
enough data
CA 02242985 1998-07-14
CA9 98 023 7
to completely fill its allocated time slice, or does not have any data to send
at all. In the
period of time allocated to that station in the TDMA, little or no data is
transmitted. This
under utilizes the medium and wastes bandwidth.
Summary of the Invention
One aspect of the invention provides a method of communication in a medium,
for a
communication network having a plurality of stations, using Medium Access
Control
protocol (having slotted carrier sensing or collision avoidance ) that
incorporates quality
of service capabilities wherein at least one of the stations is capable of
generating a
beacon for assigning priority levels for each priority station on the network,
wherein:
a station, before transmitting information on said network, attempts to detect
the
presence of a beacon for the network, and if the presence of a beacon is not
detected,
adopts the status of a beacon and transmits a beacon message to other stations
in the
network.
Another embodiment of the invention synchronizes the count down of collision
avoidance slots in CSMA-CA MAC protocol by the transmission of a MAC layer
control
frame that is uniquely distinguishable from upper network layer data frames.
This
frame is called a beacon. The information contained in the beacon frame
identifies the
MAC layer addresses of a set of devices which have been allocated exclusive
use of
priority contention slots within the range of the device transmitting the
beacon. The
beacon also contains information to tell these priority device the maximum
amount of
time they may transmit priority data in the medium, the maximum time between
beacons and the time duration of the beacon. This information allows the
priority
devices to determine certain quality of service parameters that they may offer
to
network clients. The beacon also contains information that the non-priority
devices
within the cell use to determine the minimum number of contention slots that
they are
required to wait upon detecting an idle channel before these non-priority
devices are
permitted to transmit on the medium. The invention discloses the process by
which
stations are assigned priority slots and how the device that generates the
beacons is
determined. The invention is able to reduce the potential interference caused
by
hidden nodes in wireless networks that employ the methods described in the
invention.
CA 02242985 1998-07-14
CA9 98 023 8
Another aspect of the invention provides a method of reducing interference in
communication in a medium using carrier modulation, for a communication
network
having a plurality of stations, using access control protocol wherein at least
one of the
stations is capable of generating a control message (SOD) that can be
transmitted to
other stations on the network to change the method of modulation being used,
wherein,
communication between stations in said network is being performed using a
first
modulation method, including:
initiating a change in the modulation method being used in the network by
sending a
control message containing identification of a second modulation method to
other
stations on the network to inform the other stations of the second modulation
method;
allowing the other stations to change the modulation method used by them to
the
second modulation method; the control message further including a direction to
those
other stations not changing to the second modulation method to instruct them
not to
transmit using the first modulation method.
Yet another aspect of the invention uses very short temporal separation
through Time
Division Multiplexing (TDM) to reduce interference when devices using
different pulse
modulation techniques of a common carrier and different physical and MAC layer
protocols are in physical proximity. The invention creates unique periods of
time in the
medium for the explicit use of one of the modulation techniques. This allows
for the
coexistence of the various modulation techniques and their accompanying
protocols.
CA 02242985 1998-07-14
CA9 98 023 9
Under certain circumstances the invention will also allow limited
interoperability
between these devices provided that the devices involved in the interoperation
are able
to communicate with at least one other modulation technique in the area of the
devices
employing the different modulation techniques. One modulation technique is
used as
the controlling modulation for one or more subordinate modulation techniques.
The
protocols of the controlling modulation are used to ensure that all devices
using that
modulation remain idle for a period of time during which another modulation
technique
may be used in the medium. The invention adds a special MAC control frame,
called a
Start of Data (SOD) frame, to the protocol of the controlling modulation. The
SOD
frame is used to inform all devices using the controlling modulation of the
next
subordinate modulation technique to be used in the medium and the period of
time that
the subordinate modulation technique will be used on the medium (called the
modulation time, or MT). After sending or receiving a SOD frame in the
controlling
modulation, no devices using the controlling modulation are permitted to
transfer data in
the controlling modulation.
If the device employing the controlling modulation is also able to understand
the
particular subordinate modulation indicated in the SOD frame, then that device
may
switch to the subordinate modulation for the MT time period specified in the
SOD
frame. Additionally, if that device contains a protocol stack that uses the
subordinate
modulation technique, and the device contains a link manager entity described
in the
invention, then that device will be able to interoperate with other devices
using the
protocols of the subordinate modulation.
The invention requires that the MAC layers in the devices using the
controlling
modulation are able to generate jamming signals in the subordinate modulation
techniques that will prevent protocols using those modulations from
effectively
transmitting in the medium.
This invention uses several building blocks that can be employed by a slotted
CSMA
(-CD) or CSMA-CA MAC protocol to provide a quality of service to network
layers above
CA 02242985 1998-07-14
CA9 98 023 10
the MAC layer that will allow isochronous communication within a network. The
invention is applicable to non-persistent CSMA MAC protocols and as well is
applicable
persistent CSMA MAC protocols if the carrier sense interval is extended to
include a
contention slot. The following sections describe each of the building blocks
and the final
section shows how the blocks can be used in a specific embodiment of the
invention to
provide improved QOS for isochronous service. The combination of the building
blocks
used provide an embodiment of the invention.
Priority Queuing Scheme : A building block used in the invention is a
mechanism by
which a MAC protocol must be able to reorder data for transmission on a
channel. Most
MAC protocols employ a simple FIFO queuing where the first block of data sent
to the
MAC for transmission is actually the first block of data to be sent on the
channel. To
provide isochronous service, the MAC protocol needs to ensure that isochronous
data
blocks are given higher priority than standard blocks of data that are not
time sensitive.
The MAC protocol requires a method to allow it to transfer the priority data
blocks
ahead of all non-priority data blocks. The priority data blocks are then sent
in FIFO
order on the channel. One of the simplest methods of achieving priority
queuing is to
simply abort any pending non priority data queued for transmission at the time
priority
data is submitted to the MAC layer for transmission. The ability to move
priority data
ahead of non-priority data in the CSMA MAC layer does not itself ensure that a
minimum transmit latency can be provided. The next packet to be transmitted
(priority
or not) is still subject to indeterminate latency as discussed under the prior
art.
Maximum Contention Interval Scheme : As already discussed, the indeterminate
latency of any transmit request submitted to the CSMA MAC layer is mainly due
to the
number of other devices simultaneously contending for the channel, the amount
of data
these devices place on the channel, and the nature of the particular CSMA MAC
protocol being employed. In order to provide time-to-live latency QOS, a
station using
the MAC protocol must abort its attempt to transmit a given block of data if
the time
required to gain access to the channel exceeds the time-to-live latency
parameter of the
QOS. This can be achieved by starting a timer (that measures the same units of
time
as the time-to-live latency QOS parameter) in the MAC layer at the same time
it begins
CA 02242985 1998-07-14
CA9 98 023 11
contending for medium access. Once the timer exceeds, the time-to-live QOS
parameter, the current transmit request must be aborted. Although this
invention is
most useful for slotted CSMA (and CSMA-CA) MAC protocols, the maximum
contention
interval timer can be employed in other CSMA MAC (non slotted as well as
persistent
CSMA MAC) protocols to provide the time-to-live QOS parameter.
Priority Slots : CSMA-CA MAC protocols incorporate the concept of contention
slots. A
contention slot is simply defined as the amount of time required to detect if
a station is
transmitting on the network. In theory, on an infinitely fast network, the
contention slot
duration is simply the amount of time required to detect a carrier signal.
However, no
physical medium is infinitely fast. Therefore, a finite amount of time is
required for a
signal to pass from one end of the network to the other. To guarantee that a
station
does not transmit just before a signal from the farthest point in the network
reaches it,
the minimum contention slot is usually defined as the amount of time for a
round trip
signal to propagate between the extreme end points of a network.
In wireless networks, stations often employ a MAC layer handshake (e.g. RTS,
CTS) to
avoid collisions with nodes that are out of range, or hidden, with respect to
the sender.
In these situations, the contention slot must also include the amount of time
to transmit
one half of the handshake signals, as well as the worst case processing time
of the
handshake at the responder and the amount of time to carrier sense the
responder's
handshake. One concept behind CSMA-CA MAC protocols is that if an idle channel
is
sensed the CSMA-CA MAC protocol will require the station to either wait a
random
number of contention slots, or a predetermined number of contention slots
before
attempting to transmit. Of course, even after this wait, the station will have
to once
again carrier-sense the medium before transmitting. While the device waits, it
is
possible that another device begins transmitting if that device happens to
choose to
wait a smaller number of contention slots. In some CSMA-CA networks a station
will
send a jamming signal/ or frame before it intends to transmit to allow
synchronization of
all CSMA-CA MACs. However, the methods we referred to are unable to avoid all
collisions. This is because it is possible that stations will choose the same
number of
CA 02242985 1998-07-14
CA9 98 023 12
contention slots to wait or may send jam signals at the same time as other jam
signals
are sent or at the same time a data frame is sent. The use of priority slots
can reduce
the probability of collision in CSMA-CA MAC protocol networks. Priority
contention slots
should be used by priority CSMA-CA devices for transferring priority data.
Given that
there are 'j' priority CSMA-CA devices in the network, then 'n' CSMA-CA
priority slots
are reserved for their exclusive use (n <= j). For the purposes of this
discussion each
priority device is assigned one, or more, of the priority slots (m), where the
assignments
begin at 0 for the first priority device and end at n-1 for the nth priority
device (0<=m<=
n-1 <j). If a device is not assigned one of the 'n' priority slots, then upon
sensing an idle
channel, the priority device must choose to wait a number of contention slots
that is at
least as large as 'n'. If a device is assigned one of the 'n' priority slots,
then upon
sensing an idle channel, the non-priority device may either choose to wait a
number of
contention slots that is at least as large as 'n', or to wait a number of
contention slots
exactly equal to 'm'. Therefore, even though the device has a priority slot,
it does not
have to use the priority slot for sending non-priority data. That is, priority
slots should
only be used to transfer priority data.
Beacons Scheme : Priority slots themselves will not avoid collisions if the
CSMA-CA
devices begin counting down contention slots at exactly the same time. For
example, a
device using contention slot 6 will collide with a device using contention
slot 8 if the
device using slot 8 begins counting down contention slots exactly 2 contention
slot
times before the device using slot 6. To avoid collisions a synchronization
event is
required to ensure all devices begin counting down contention slots at the
same instant.
In this invention, the synchronization event is provided by a unique MAC frame
that
indicates that priority traffic will follow the frame (if there is any present
in the priority
devices). This synchronization frame is called a Beacon. The beacon is
distinguishable from regular MAC data frame and is used by the MAC protocol
for
synchronization not for the communication of upper layer data. For CSMA-CA MAC
protocols that use separate MAC control and MAC data frame formats, this
application
of the invention is straightforward - the beacon is sent as MAC control frame.
MAC
protocols that do not employ control frames may use a special multicast
address for the
CA 02242985 1998-07-14
CA9 98 023 13
purpose of QOS management. Some CSMA-CA protocols may employ similar
concepts but are very limited in their scope of operation. Some send special
non data
synchronization pulses, and some will send small frames to announce the desire
to
transmit, or small frames announcing that synchronized data transfer is about
to
commence. Although these protocols may work well in a wired network, they
begin to
break down in wireless networks because of hidden nodes and overlapped network
cells. For example consider the wireless networks depicted in Figure 2 in
which a
device 26 in a network cell 21 (P1 in the left cell) is assigned the same
priority slot as
another device 24 in an overlapped cell 20 (P1 in right cell). Since wireless
devices are
highly mobile, it is possible that device 26,P1, from the left cell 21 will
move from a
region where it is unable to hear (or interfere with) devices in the right
cell 20 to a region
22 where it is able to hear (and interfere with) devices in both cells 20 and
21. Suppose
now that the left device 26 moves into overlapping region 22. If device P0,
23, in the
right cell 20 initiates a standard CSMA-CA contention period, then both
devices 26 and
24 will send their data at the same time resulting in a collision.
The beacon is able to solve this problem because either P1 device 26 or 24 is
able to
distinguish between a beacon sent from within its own cell as opposed to a
beacon
heard from another cell. This is achieved by 2 mechanisms inherent in the
format of
the beacon. First, since the beacon is a special MAC (control) frame, it will
carry a
Source Address (SA), like all other MAC (control) frames. Since the invention
requires
that the device that is responsible for generating the beacon is also
responsible for
assigning any priority device its priority slot (discussed later), every
priority device
knows the identity of the device to whose beacons it should respond. Second
the data
contained in the beacon is an ordered list of the MAC layer addresses of the n
priority
devices in the cell that are the n registered users of that device's beacon.
The ordinal
position of the MAC address in the list dictates the priority slot that that
MAC address is
able to use for its priority data.
The 2 mechanisms employed in the beacon that allow a priority device to ensure
that it
only transmits its priority data at the appropriate time also allow the device
generating
the beacon to dynamically reassign priority slots. The ability to dynamically
reassign
CA 02242985 1998-07-14
CA9 98 023 14
priority slots means that the generator of the beacon can minimize the number
of
priority slots used within the cell which reduces non-priority device's
channel access
latency times. For example, if there were j registered priority devices in the
cell, where j
is some integer multiple, x, of n (i.e. j = x * n), then the device generating
the beacon
could simply generate 1 beacon announcing j slots to all j priority devices.
Or the
device could generate x successive beacons, each announcing n unique MAC
addresses that are able to transmit their priority data in the appropriate
contention slot.
In the first case, on average, all non-priority devices will experience a
longer transmit
latency time. In the second case, on average, the non-priority devices will
experience a
shorter transmit latency but the priority devices will, on average, experience
a longer
latency time.
Isochronous Implementation Scheme
This section gathers information from the previous sections to present the
steps
required to ensure that once devices in the network are assigned unique
priority slots
from a unique device, deterministic latency periods can be provided. The next
section
describes how the priority slots are assigned and the process by which a
station is
elected to generate the beacons. Networks operating in this manner are
referred to as
CSMA-CA with Beacon MAC protocols, (CSAM-CAB).
1) An isochronous device must have the ability to send priority data, in FIFO
order
when required, ahead of all non-priority data by means of priority queuing. It
is not
necessary to abort a non-priority transmission in progress when priority data
is
submitted to the MAC.
2) Every contention slot used in every station (priority as well as non-
priority) must be
of a fixed length and large enough to accommodate the worst case time to
detect an
active channel and all stations must be using contentions slots of equal
duration.
3) Any device that does not have a priority slot must wait a minimum number of
contention slots that is equal to, or greater than, the number of priority
slots currently
distributed in the network before attempting to transmit when the channel is
detected as idle.
CA 02242985 1998-07-14
CA9 98 023 15
4) If a device loses access to the medium in while contending, it can resume
counting
down contention slots from where it left off before the another device began
transmitting if the remaining contention slot count is still larger than the
current
number of priority slots distributed in the network; otherwise the device must
chose
a new contention slot according to rule 3.
5) Devices using a priority slot are only bound by rule 4 when transmitting
non-priority
data. When attempting to transmit priority data, they may continue counting
down
contention slots as soon as the medium is once again sensed as idle.
6) The device using priority slot 0 must send the Beacon frame at regular
intervals
(determined by the minimum latency and guaranteed bandwidth QOS parameters).
The beacon contains the MAC layer addresses of the n devices that have been
granted priority slots. The ordinal position of those MAC addresses determines
which priority slots) each device has been assigned. The Beacon must be sent
before any priority data from Device 0 is sent.
7) A station that recognizes its MAC address in the beacon, and the beacon SA
as the
MAC address of the station that assigned its priority slot, will transmit its
priority data
in the slot indicated by the ordinal position of its MAC address in the
beacon. If this
differs from the previously allocated priority slot for that device, then the
device has
been assigned a new priority slot.
8) In order to keep using a priority slot, other than slot 0, a non-beacon
generating
priority device must be able to hear the broadcast beacon frame from the
device
using priority slot 0. Once a device using priority slot n hears the beacon,
and that
device has priority data to transfer, it will use it's assigned slot to
transfer up to a pre
determined amount of priority data. This ensures that all priority data will
be
transferred in the first n-1 contention intervals after the beacon.
In the absence of any interference, these steps would be sufficient to ensure
that a
device using a priority slot will be able access the medium in a finite,
deterministic
period of time. Step 3) guarantees that if a device using a priority slot and
a device not
using a priority slot are both given data to transmit at the exact same time,
then the
device using the priority slot will win access to the medium before the other
device.
CA 02242985 1998-07-14
CA9 98 023 16
Steps 2) to 4) ensure that even when there are other devices that have
previously lost a
reservation any device using a priority slot will still win access to the
medium before all
other devices not using priority slots.
Suppose the particular MAC protocol requires that no single station can
transmit
non-priority data on the medium for any more than the Non-Priority Access Time
(NPAT). Also, suppose that each priority device can only transmit priority
data on the
medium for no more than the Priority Access Time (PAT). Suppose the Beacon
required BT time to transmit and is sent every Beacon Interval Time (BIT).
Finally
suppose there are 'n' priority slots allocated in the network. Note that in
the equations
that follow the duration of the contention slot is not taken into account.
This scheme
ensures that no matter how many devices there are in the network, nor how much
data
those devices are transmitting, the worst case maximum transmit latency for a
priority
device (in the absence of interference) is always deterministic and given by
the
following formula:
(1 ) Latency = BIT - n * PAT -BT+ NPAT + BT + (n-1 ) * PAT
= BIT + NPAT - PAT
On average, over time, each priority device is able to get access to the
medium for a
period of time of PAT every BIT period. Therefore, on average, over time,
every priority
device is guaranteed PAT/BIT*100 % of the channel's base baud rate.
(2) Priority bandwidth = PAT / BIT * channel bandwidth
2s Extensions
The definition of the beacon can be extended to include the cell parameters
BIT, NPAT,
BT and PAT. This allows the beacon generator to dynamically change the cell
parameters. In addition, to an ordered list of MAC addresses, the beacon
definition can
further be enhanced to include unique PAT times for every MAC in the beacon
list.
This would allow the beacon generator to dynamically modify the bandwidth
allocated to
CA 02242985 1998-07-14
CA9 98 023 17
each priority device and allow the priority devices to request varying
guaranteed
bandwidths. With this beacon definition the worst case transmit latency is:
(3) Latency. = BIT - sum(for j=0 to n-1 )of(PAT;) -BT+ NPAT + BT
+ sum(for j=0 to n-1, j != i)of(PAT;)
=BIT+NPAT-PAT;
And the bandwidth allocated to device i is:
(4) Priority bandwidth. = PAT. / BIT * channel bandwidth
Finally, if the cell were operated in a TDMA manner than NPAT in equation 1
would be
0. The BIT would also be specified in terms of the number of priority devices
in the cell,
BIT = n * PAT. (The registration process defined in the next section would
also need to
be enhanced.) Therefore equation 1 could be reduced to:
(5) Latency = (n-1 ) * PAT
If every station were assigned varying amounts of bandwidth according to
equation 4,
then the worst case latency is:
(6) Latency. = sum(for j=0 to n-1,j!=i)of(PAT;)
Allocating and Releasing Priority Slots
Another aspect of CSMA-CAB networks in accordance with this invention involves
acquiring use of a priority slot(s), releasing a priority slots) and
determining which
device will use slot 0. To simplify the discussion, the device using priority
slot n will be
referred to as Device n. The broadcast frame that Device 0 must transmit every
BIT
period will be called the (isochronous) Beacon. These frames must be consumed
at
the MAC layer without being passed up to the network or higher layers. As
previously
mentioned, this may be achieved through MAC layer control frames or through a
CA 02242985 1998-07-14
CA9 98 023 18
special multicast MAC address reserved for CSMA-CAB networks. In the following
text
the beacons are assumed to be transmitted as MAC control frames.
Establishing the Presence of a Beacon Generator in the Cell
We have found that for advantageous performance, before a device is permitted
to
transmit on the network, it must first wait a period of time at least 2
default BIT periods
long to allow sufficient time to detect a beacon. (A guaranteed minimum
bandwidth and
maximum frame size determine the default maximum BIT, see equation 4.) If a
beacon
is heard within this interval, then the new device will know the number of
allocated
priority slots within the network and hence the minimum number of contention
slots it
must wait before attempting to transmit when the medium is sensed as idle. If
the
number of allocated priority slots changes as successive beacons are heard
then so too
does the minimum number of contention slots that a non-priority device (or a
priority
device sending non-priority data) is required to wait before attempting to
transmit when
the medium is sensed as idle.
On the other hand, if after having listened for a period of time at least 2
default BIT
periods long, the Beacon is not heard, then the local device must start
issuing the
beacon and assume that it is Device 0. (This is required even if the device
does not
wish to transfer priority data.) The first beacon generated by Device 0 must
not be sent
using a priority slot. In the case where the device assuming Device 0
responsibility
never heard a previous beacon, at must wait one contention slot before sending
its first
beacon. In the case where the device is no longer able to hear the beacons of
the
device from which it was previously allocated a beacon, it must wait a minimum
number
of contention slots equal to the priority slot it was assigned on the last
beacon heard.
This helps to eliminate beacon collisions when the previous beacon generator
suddenly
stops beaconing in a cell with allocated priority slots.
Note that this process ensures that before any device in the network begins
transmitting, there will already be 1 allocated priority slot for Device 0.
Therefore the
CA 02242985 1998-07-14
CA9 98 023 19
minimum number of contention slots that a non-priority device must wait before
attempting to transmit when the medium is sensed as idle is always at least 1.
If a device that does not wish to transfer priority data becomes the beacon
generator, it
may transfer Device 0 status to the first device that registers it's desire to
allocate a
priority slot (see below).
Requesting a Priority Slot From Device 0
A device that wishes to acquire a priority slot must send a special MAC
control frame to
Device 0, informing Device 0 that it wants to use a priority slot.. The device
must now
wait for the next Beacon. If the Beacon identifies the device as Device n,
then the local
device knows it has acquired priority slot n. If the Beacon does not contain
the MAC
address of this device, then this device has not been assigned a priority
slot. In this
case, the device resends the control frame requesting the use of a priority
slot. This
may be done automatically in the MAC or at the explicit request of the upper
network
layer.
If there were multiple devices simultaneously requesting priority slots, their
requests will
most likely collide meaning that the beacon generator would not receive either
request.
Therefore the next beacon will be void of either requesting device's MAC
address and
they will have to resubmit their requests. (Again this may be done
automatically in the
MAC or at the explicit request of the upper network layer.) If the beacon
generator
does happen to receive both requests the next beacon generated will indicate
that one
device is Device x, and the device is Device y.
Multiple Beacons Generators in a Cell
In the embodiment of this invention described herein, it is assumed that in
each network
cell, there is only 1 beacon generator (you will recall that device with
priority level 0, P0,
is used as the beacon generator). However, in a wireless network, where
devices are
mobile, it is possible that one beacon generator will move into a region where
it will be
heard by another beacon generator. This is an unstable configuration and may
defeat
CA 02242985 1998-07-14
CA9 98 023 20
the algorithm if the beacon generators attempt to transmit their beacons at
exactly the
same time all the time.
In the situation where Device 0 hears another Beacon, the MAC with the higher
numeric
MAC address will stop sending Beacons. This may mean that some devices in the
cell
will no longer be able to hear any beacons (i.e. those devices that are only
able to hear
the beacons from the beacon generator that just stopped sending beacons). The
rules
for beacon generation will ensure that one or more of those devices that are
unable to
hear a beacon will automatically start beaconing themselves. This may in turn
lead to
beacons being heard by beacon generators. After some period of time, the new
beacon generators will be determined and the network will once again return to
the
default, stable, condition whereby each cell has only 1 beacon generator.
An enhancement to the basic algorithm that may reduce the contention for
Device 0
status just described. Once the beacon generator detects another beacon
generated
by a device with a numerically smaller MAC address requiring it to stop
generating
beacons of its own, it may inform all Devices that had requested priority
slots with it that
they can no longer use their priority slots and inform them of Device 0's MAC
address in
a special control frame. It is expected that either approach will cause some
disruption
in the isochronous transfers until the new priority slots are allocated from
the new
Device 0(s).
Devices in the Overlapping Region of Overlapping Network Cells
In networks where all devices are able to hear all other devices, the previous
rules on
beacon generation and priority slot registration ensure that all priority slot
assignments
in the network are unique. As such, there will only be one beacon generator
(Device 0).
However, when these concepts are extended to wireless networks, it is possible
that
one group of devices may not be able to hear all other devices that are in the
area of
the entire network. For example, if a wireless device has a range of 100
meters, than if
3 devices, A, B and C were in a line each 90 meters apart, than all devices
are in range
of a subset of all devices in the wireless network. But the devices at the end
points will
CA 02242985 1998-07-14
CA9 98 023 21
be unable to hear each other. This phenomenon is referred to as the hidden
node
problem.
In the context of this invention, a cell is defined as all devices that are
able to
communicate with Device 0. However, even if the beacon generators are far
enough
apart to ensure that they do not hear each other (and can therefore form their
own cell),
devices at the cell boundaries can be in a position where they are able to
hear devices
in the other cell. In situations where a priority device is in a position
where it is able to
hear multiple beacons and the beacon generators are unable to hear each other,
it is
possible that the beacons will all collide at this device if they are
transmitted at the
same time. When this happens, the device will not be able to hear a beacon and
may
not transfer any data.
If a non-priority device is able to hear multiple beacons it must not attempt
to transmit in
a contention slot lower than the largest priority slot allocation indicated in
the multiple
beacons. This ensures that non-priority devices in overlapped network cells do
not
interfere with any priority data in either cell.
Devices Not in the Overlapping Region of Overlapping Network Cells
Devices that are not present in the overlapping region of overlapped cells are
considered hidden nodes with respect to the cells) from which they are absent.
These
devices can interfere with priority and non-priority traffic in the overlapped
cell(s). This
invention does not provide a mechanism to eliminate the interference caused by
multiple hidden nodes in every situation; however, the invention will
significantly reduce
the hidden node interference for priority data transmissions originating from
or destined
to the overlapping region of overlapping cells (see the wireless extension in
the next
section)
CA 02242985 1998-07-14
CA9 98 023 22
Extension: Beacon Splitting Wireless for the Purpose of Reducing Hidden Node
Interference
In the discussion of the previous section it was stated that so long as the
beacon
generators in overlapped cells do not continually simultaneously generate
their
beacons, devices in the overlapping regions would be able to detect that they
are in an
overlapping region. Therefore, these devices would know the number of
allocated
priority slots in each cell because of the information contained in the beacon
frames. A
device in the overlapping region would then do the following. First it would
tell the
beacon generators) in the cell(s), in which fewer priority slots were
allocated, to
artificially allocate dummy priority slots (i.e. priority slots assigned to
the NULL MAC
address, which is used as a dummy address). Secondly, each priority device in
the
overlapping region would inform its own beacon generator that it is in an
overlapping
region. This information would be conveyed in MAC control frames.
This would allow the beacon generator of the priority device in the
overlapping region
the opportunity to send multiple beacons to service the priority devices in
its cell. In
some cases, this beacon generator may be able to use this information to alert
potentially hidden nodes of a pending priority transfer. For example, in
wireless
networks where hidden nodes are a problem, the MAC protocol often employs a
handshake mechanism (e.g. RTS CTS) to eliminate interference from hidden
nodes.
Suppose that a beacon generator realizes that its n priority devices are split
in x (x >= 2)
overlapped cells (as a result of feedback from these devices). Instead of
generating a
single beacon with priority slot information for all priority devices in the
cell, the beacon
generator could generate multiple beacons where each is meant to serve the
subset of
the n priority devices in the cell that are in a specific overlapping region.
By performing
the MAC protocol handshake with a device in the overlapping region, hidden
nodes in
the vicinity of the overlapping region would be required to remain idle for a
number of
contention slots equal to the allocated number of slots in its own cell. But
since the
device in the overlapping region previously informed the beacon generator of
the
overlapped cell to allocate dummy slots, the hidden node will not attempt to
transmit for
x contention slots, where x is the greater of the number of allocated priority
slots in each
CA 02242985 1998-07-14
CA9 98 023 23
cell. Therefore the hidden node will not be able to interfere with the
priority data
transfer initiated by priority devices in the overlapping region until after
the priority
transfers authorized by the beacon completed. If the split beacon indicated
that the
number of priority slots in the cells was reduced, then the beacon generator
in the
overlapped cell would again be informed of this and could eliminate some of
its dummy
priority slot allocations. Once a steady state condition was reached, hidden
nodes
would not be able to interfere with the priority transfer in the overlapping
region. This
process could be repeated for all overlapped cells.
Wireless Extension: Resolving Beacon Contention in Overlapping
It was noted that if Device Os in overlapped cells transmitted beacons at the
same time
all the time that devices in the overlapping region would not be able to
detect they are in
an overlapping region. But even if this did not initially occur and the
process described
above was followed, problems would occur if the beacon generators in the
overlapped
cells attempted MAC handshakes with different devices in the same overlapping
region.
To prevent this a method is needed to ensure that devices in an overlapping
region
register with the same beacon generator. This can be achieved by requiring a
priority
device in an overlapping region to release its priority slot if it was not
gained from the
highest MAC address of the beacon generators heard. Before releasing the
priority
slot, the affected priority device would request a priority slot from the
beacon generator
with the highest MAC address (somewhat arbitrary decision, important point is
that all
devices in the overlapping region are registered with the same beacon
generator).
Finally, it should be noted that because this method coordinates the priority
transfer in
overlapped cells, the maximum latency times are extended by the amount of
priority
data transfer in the overlapped cell(s).
Releasing Priority Slots
When a station no longer wishes to use a priority slot the reverse process is
followed.
A MAC control frame is sent to Device 0, to release slot n. Upon hearing the
next
Beacon if slot n is marked as idle or owned by another device than the local
device no
CA 02242985 1998-07-14
CA9 98 023 24
longer owns priority slot n. When Device 0 no longer wishes to use priority
slot 0, it sets
the 'pass beacon' field to some other priority slot device (This is not
essential since
beacon generators will be created in a cell by the nature of the protocol
followed to
establish a beacon generator in the cell. This extra step reduces the
disruption to
priority data transfer). When the Device using this slot hears the next Beacon
identifying it as the new beacon generator, that device will changes its
identity to Device
0 and will be responsible for sending Beacons from that point on. If the
original Device
0 does not hear a Beacon within 2, or more default BIT intervals, it must
reassign the
Beacon. The decision of which priority device to pass the beacon generating
responsibility to can be arrived at by heuristical methods, or arbitrarily
chosen. The
exact method used is not key to the invention but may disrupt operation (for
example it
would be undesirable to pass beacon generating to a device in the overlapping
region
of overlapped cells since this may alter the identity of many beacon
generators.
Other Consideration
In situations where Device 0 simply vanishes, Device 1 (or the device using
the smallest
priority slot) will usually assume the responsibility of generating the Beacon
after at
least 2 BIT periods by nature of the method of establishing a beacon
generator. In
doing so, Device 1 will become Device 0 remove all other entries from the list
of MAC
addresses sent in the beacon.
Periodically Device 0 should reassign priority slots to ensure that there are
no gaps in
the Beacon. This also has the effect of reducing the maximum number of
allocated
priority slots and affords non-priority device a lower average transmit
latency time.
Detailed Description of the Preferred Embodiment of another Aspect of the
Invention
Referring to Figure 3 this embodiment of the invention is demonstrated though
a
coexistence scheme designed into a controlling modulation MAC protocol layer,
33,
that will allow it to coexist with an arbitrary subordinate modulation MAC
protocol layer,
30. The invention will allow the 2 MAC protocol layers, 30 and 33, to
interoperate with
CA 02242985 1998-07-14
CA9 98 023 25
other such devices employing both MAC protocol layers or other devices
employing one
or the other MAC protocol layers. Both physical layers, 34 and 35, employ
different
pulse modulation techniques of a common infrared carrier signal. Without using
the
methods in this invention, these protocols will interfere with one another if
they are
placed within range of each other. Because each protocol uses a different
modulation
encoding of the a common carrier, they are not able to directly communicate
with one
another.
In this embodiment, the controlling physical layer, 34, is able to generate a
jamming
signal in the modulation of the subordinate physical layer, 35. The jamming
signal so
generated ensures that other subordinate MAC physical layers in other devices
in the
networks will be prevented from transmitting data in the medium for a certain
period of
time, called the Idle_From Jam time. The controlling MAC protocol, 33, directs
the
controlling physical layer, 35, to generate the jamming signal. The jamming
signal will
have to be retransmitted if the controlling modulation MAC protocol, 33,
remains in
control of the modulation for a period of time greater than the Idle_From Jam
Time.
The controlling modulation MAC protocol manager, 33, will therefore direct the
controlling modulation physical layer, 34, to generate jamming signals at the
appropriate interval.
The controlling modulation MAC protocol layer, 33, sends a SOD frame in its
own
modulation to inform other controlling modulation MAC protocol layers when the
modulation will be changed to that of (one of) the subordinate modulation. The
SOD
frame also informs the control modulation MAC protocol layers of the amount of
time
the subordinate modulation will be used in the medium.
The link manager, 32, uses the services of the controlling modulation MAC
protocol
layer, 33, to generate the SOD from with the required MT value when the
subordinate
MAC protocol manager, 31, determines that the subordinate modulation MAC
layer, 30,
requires access to the medium. The subordinate MAC protocol manager, 31, is
able to
determine this by knowing the protocol flow of the subordinate modulation MAC
layer
CA 02242985 1998-07-14
CA9 98 023 26
protocol, 30. The subordinate MAC protocol manager, 31, queues data frames
from
the subordinate MAC protocol manager, 30, until sufficient data has been
queued to
warrant a transfer on the medium, or until such time as it realizes the
subordinate
modulation MAC protocol flow will break down because of being blocked from the
medium while the controlling modulation is being used.
The subordinate MAC protocol manager, 31, is able to block data transfer
between the
subordinate modulation MAC protocol layer, 30, and the subordinate modulation
physical layer, 35, by placing itself in the path of this data flow. When the
controlling
modulation is being used in the medium, the subordinate MAC protocol manager,
31,
may either queue any data requests from the subordinate modulation MAC
protocol
layer, 30, or simply discard the data. Similarly when the controlling
modulation is used
the subordinate MAC protocol manager, 31, will discard any data the
subordinate
modulation physical layer believes it is receiving.
When the subordinate MAC protocol manager, 31, determines that its subordinate
modulation MAC protocol layer, 30, requires medium access it requests the link
manager, 32, to request the controlling modulation MAC protocol layer, 33,
generate
the SOD frame indicating the use of the subordinate modulation for a certain
period of
time. When this frame has been transmitted in the controlling modulation, the
controlling modulation MAC protocol layer, 33, wil stop directing the
controlling
modulation physical layer to generate jamming signals. The controlling
modulation
MAC protocol layer, 33, will also indicate the new modulation in effect in the
medium to
the link manager, 32; which in turn will convey the information to all
subordinate
modulation protocol managers, 31. After the subordinate modulation protocol
manager,
31, is informed that its subordinate modulation is in effect, it will no
longer block
communication between the subordinate modulation MAC protocol layer, 30, and
the
subordinate modulation physical layer, 35. This will allow communications in
the
subordinate modulation to occur between subordinate modulation MAC protocol
layers,
30 for the period of time specified in the SOD frame.
CA 02242985 1998-07-14
CA9 98 023 27
After the period of time during which the subordinate modulation may be used
in the
medium, which was contained in the SOD frame of the controlling modulation,
the
controlling modulation MAC protocol layer, 33, will inform the link manager,
32, that the
controlling modulation is once again in control of the medium. The link
manager, 32,
will then inform all subordinate modulation protocol manager, 31, that it must
once
again resume blocking the transfer of data between the subordinate modulation
MAC
protocol layer, 30 and the subordinate modulation physical layer, 35.
Pseudo Code For the First Aspect of the Invention
Notes: The pseudo code that follows illustrates an embodiment of the basic
invention.
None of the enhancements to the base algorithm have been included. In
particular, the
wireless extensions dealing with hidden nodes and some overlapping cell
details are
not shown in the implementation. Also the implementation uses:
- A fixed value for PAT, NPAT, BIT
- Only a single priority slot is assigned to any 1 MAC address
- The beacon generator does not partition beacons for sets of priority
devices.
It will be appreciated that when appropriately licensed the pseudo code may be
used in
the implementation of the invention in software recorded on a medium that may
be
used by stations of a network or in circuitry such as micro code used in the
stations.
Init Routine:
BeaconHeard = FALSE;
2$ MinimumContentionSlot = 0;
MaximumContentionSlot=MAXIMUM NUMBER_OF CONTENTION SLOTS;
NumberAssignedPrioritySlots = 0;
RemainingContetnionSlots = 0;
MyPrioritySlot = 0;
MissedBeaconCount = 0;
Beaconldentity = NULL;
PendingTransmitFrameType = NULL;
PendingTransmitData = NULL;
PhysicalCarrierState = NO CARRIER;
3$ SIotCIockTimerHandle = NULL;
NPAT = Maximum time a non-priority device may send data on the channel;
PAT = Maximum time a priority device may send data;
CA 02242985 1998-07-14
CA9 98 023 28
BIT= Beacon Interval Time
BT = Time to transmit beacon
WaitingForPhysicalTransmitComplete = FALSE;
RequestTimeout( interval = BIT, timeout Routine = BeaconTimeoutHandler );
output: Integer
Random Integer
(
input: LowestValueInSelectionRange,
input: HighestValueInSelectionRange
local variable: ReturnValue;
ReturnValue =
choose a number at random at least as large as the
LowestValueInSelectionRange and no larger than
HighestValueInSelectionRange at random;
return( ReturnValue );
PhsicalLayerCarrierSenseCallback
(
input: CarrierState
/*
This MAC callback routine is called by the physical layer when it detects a
' change in the carrier signal state in the medium. When the medium is idle
* and a carrier is detected (i.e. another station is starting to transmit),
this
routine will be called with CarrierState = ACTIVE CARRIER. When the
transmitting station completes its transmission, this routine is called again
* with CarrierState = NO CARRIER
~/
PhysicalCarrierState = CarrierState;
IF( CarrierState== NO_CARRIER )
IF( PendingTransmitFrameType != NULL )
Start_Slot Clock Timer();
)
4S ELSE
(
Cancel_Slot Clock_Timer();
CA 02242985 1998-07-14
CA9 98 023 29
IF( RemainingContentionSlots < MinimumContentionSlot )
IF( PendingTransmitFrameType == NON PRIORITY_DATA )
RemainingContentionSlots = Random_Integer( MinimumContentionSlot,
MaximumContentionSlot );
}
}
}
Start Slot Clock Timer
r
' All transmit requests must eventually come through this routine.
* We are not allowed to transmit until a beacon is heard. Therefore the slot
clock is only actually stated
if we have recently heard the beacon. If a beacon has not been heard recently,
then the current xmit
' data is held pending until we once again start hearing beacons (or start
generating them )
if( BeaconHeard )
(
if( RemainingContentionSlots > 0 )
SIotCIockTimerHandler = RequestTimeout( interval = CONTENTION SLOT TIME,
timeout_Routine = Slot Clock_Timeout );
l
else
Slot Clock Timeout();
}
Cancel Slot Clock Timer
call into operating system to disable timer activity on handle
SIotCIockTimerHandler
}
Slot Clock Timeout
/*
This routine is called every CONTENTION SLOT TIME period while there is a
pending.
* The slot clock timer period is a constant for the particular MAC protocol
being used.
* Whenever the slot clock timer is enabled, it will always count a complete
slot clock
CA 02242985 1998-07-14
CA9 98 023 30
* intervals. If the slot clock timer is started with a 0 value to count down,
this routine
* is immediately called.
*/
IF( RemainingContentionSlots == 0 )
{
WaitingForPhysicalTransmitComplete = TRUE;
Issue_Physical Layer_Transmit( PendingTransmitData );
)
ELSE
{
RemainingContentionSlots = RemainingContentionSlots - 1;
SIotCIockTimerHandler = RequestTimeout( interval = CONTENTION SLOT TIME,
timeout_Routine = Slot Clock Timeout );
)
l
Send_Frame_Complete
{
/*
* This routine is called by the physical layer when it has completed
transmitting
* the frame data from the Issue_Physical Layer Transmit physical layer
routine.
"/
WaitingForPhysicalTransmitComplete = FALSE;
IF( there is a queued Beacon for transmit )
{
/*
* This check is really only necessary if the station does not choose to abort
a transmit in progress
* when a Beacon needs to be transmitted.
*/
remove beacon data from the beacon queue
Send_Frame_Routine( BEACON, BeaconData );
)
ELSE
{
IF( PendingTransmitFrameType == BEACON )
/*
* The beacon has just been transmitted by this station. Therefore this station
is using
* priority slot 0. Therefore any queued priority data can now be sent = there
is no need
* to contentd, everyone else will be waiting for at least one contention slot.
*/
IF( there is more priority data queued )
{
PendingTransmitFrameType = PRIORITY_DATA;
CA 02242985 1998-07-14
CA9 98 023 31
PendingTransmitData = dequeue up to PAT of priority data from the priority
data queue;
WaitingForPhysicalTransmitComplete = TRUE;
Issue_Physical Layer Transmit( PendingTransmitData );
}
ELSE
PendingTransmitFrameType = NULL;
}
ELSE
(
PendingTransmitFrameType = NULL;
IF( there is more non-priority data queued )
Send_Frames_Routine( NON PRIORITY_DATA,
dequeue upto NPAT of non priority data from non-priority data queue);
}
Send Frames Routine
(
2$ input: frame_type,
input: frame_data
/*
* It is assumed that the HW/ Physical layer can transfer multiple frames at
once. The frame data may actually
* contain multiple frames. The restriction on the data size is that for a
(non)priority transfer,
* frame_data in bytes * 8 bits per byte / channel bandwidth <_ (NP)AT
* Is another frame already pending for transmit?
*/
IF( PendingTransmitFrameType != NULL )
(
/*
* Abort it we're trying to send priority data or a beacon
*/
IF( frame_type != NON PRIORITY_DATA )
(
Cancel Slot Clock_Timer();
requeue the pending data at the head of the non priority transmit queue;
}
ELSE
CA 02242985 1998-07-14
CA9 98 023 32
l'
* This should not occur. More error handling should be added.
*/
internal error => priority data and beacons should never overlap;
Cancel Slot Clock Timer();
PendingTransmitFrameType = frame_type;
PendingTransitData = frame data;
/*
* Choose the number of contention slots to wait based on frame type.
' The pending transmit data needs to be formated into an appropriate physical
layer format and the MAC
* needs to distinguish between control frames (sent between MAC layers and
upper layer data frames.
I S */
choose( frame_type ) as one of:
(BEACON):
(
RemainingContentionSlots = 0;
PendingTransmitData is formatted as MAC control frame;
);
( PRIORITY DATA ):
RemaingContentionSlots = Assigned_Priority_Slot;
PendingTransmitData is formatted as upper layer data frame;
);
( NON PRIORITY_DATA ):
(
RemainingContentionSlots = Random_Integer( 0, MaximumContentionSlot ) +
MinimumContentionSlot
PendingTransmitData is formatted as upper layer data frame;
);
( REQUEST_PRIORITY SLOT CONTROL_FRAME )
3S ( RELEASE PRIORITY_SLOT_CONTROL_FRAME )::
(
RemainingContentionSlots = Random_Integer( 0, MaximumContentionSlot ) +
MinimumContentionSlot
PendingTransmitData is formatted as MAC control frame;
)
l
/*
* Check for a valid carrier. We only begin counting down contention slots once
the medium is free.
*/
IF( PhysicalCarrierState = NO_CARRIER )
(
CA 02242985 1998-07-14
CA9 98 023 33
Start Slot Clock Timer( RemainingContentionSlots );
MAC Transmit Non Priority_Data
(
input: data frame
{
queue the data frame on the non-priority data queue;
IF( WaitingForPhysicalTransmitComplete == FALSE )
{
Send_Frame_Routine( NON_PRIORITY_DATA,
I S dequeue upto NPAT of non priority data from non-priority data queue);
MAC_Request_Priority_Slot
/*
* In this sample implementation, each MAC station is only able to have 1
priority slot.
* An enhanced implementation would allow multiple priority slots to be used by
any station.
*/
IF( MyPrioritySlot == 0 ) AND ( Beaconldentity != NULL ) AND ( Beaconldentity
!= MyMACAddress )
{
Format MAC control frame to request a priority slot from the Beaconldentity
_ _ _Send_Frames_Routine( REQUEST PRIORITY SLOT CONTROL_FRAME,
formatted control frame );
ELSE
{
IF( MyPrioritySlot != 0 ) OR ( Beaconldentity == MyMACAddress )
{
indicate that priority slot already assigned
ELSE
{
fail the request
)
)
)
CA 02242985 1998-07-14
CA9 98 023 34
MAC_Release_Priority_Slot
(
/*
* The MAC could track the amount of time between successive calls to MAC
Transmit Priority_Data
$ * and automatically release the priority slot (by calling this routine). In
this simple implementation,
* once the priority slot has been allocated, it is left open until the upper
layer explicitly releases it.
IF( MyPrioritySlot != 0 )
Format MAC control frame to release priority slot from the Beaconldentity
_Send_Frames_Routine( RELEASE_PRIORITY SLOT_CONTROL FRAME,
formatted control frame );
/*
* This simple implementation does not reassign the beacon responsibility
1$ */
MAC_Transmit Priority_Data
(
input: data frame
IF( MyPrioritySlot != 0 ) OR ( Beaconldentity = MyMACAddress )
(
queue the data frame on the priority data queue;
/'
* Must wait for the next beacon to send priority data.
*/
)
ELSE
(
/*
* Faile the request. This should indicate to the upper layer that this device
does not own a
3$ * priority slot and therefre can not send priority data. This will cause
the upper layer to (re)request t
* a priority slot.
*/
BeaconTimeoutHandler
local variable: slot delay_on first beacon;
IF( Beaconldentity == MyMACAddress )
CA 02242985 1998-07-14
CA9 98 023 35
IF( WaitingForPhysicalTransmitComplete == FALSE )
SendFrame( BEACON_FRAME, BeaconList );
ELSE
queue beacon data Beaconl_ist;
}
}
ELSE
(
IF( BeaconHeard == FALSE ) THEN
(
MissedBeaconCount = MissedBeaconCount + 1;
IF( MissedBeaconCount >= MAX_MISSED BEACON COUNT )
MissedBeaconCount = 0;
f
* The Beacon generator hasn't been heard in awhile.
* Assume ownership of the beacon.
*/
IF( MyPrioritySlot != 0 )
slot delay_on first beacon = MyPrioritySlot;
}
else
(
slot delay_on first beacon = 1;
}
IF( PendingTransmitFrameType != NULL )
f
!'
3$ * (Re)Enable transmit operation
*/
Start_Slot Clock();
remove any pending or queued RequestPrioritySlot control
frames
}
Beaconldentity = MyMACAddress;
BeaconList = ( empty };
MinimumContentionSlot= 1;
MyPrioritySlot = 0;
NumberAssignedPrioritySlots = 1;
CA 02242985 1998-07-14
CA9 98 023 36
RequestTimeout( _interval = BIT + ( slot delay_on first beacon * CONTENTION
SLOT TIME,
timeout Routine = BeaconTimeoutHandler );
S
Receive Callback Routine
(
input: data
)
/*
* Determine if this is upper layer data or a MAC layer control frame.
* Note: Received data must be transmormed from physical layer data into mac
layer data. Only non
1 S * MAC control frames are sent to the upper layers.
*/
IF( data is formatted as an upper layer data packet )
(
transfer data to upper network layer for processing
)
ELSE
(
/*
* This is a MAC control frame.
2S */
choose( frame_type ) as one of:
(
(BEACON COTROLFRAME):
(
BeaconHeard = TRUE;
Process_Beacon( beacon data );
)~
( REQUEST_PRIORITY SLOT CONTROL FRAME ):
3S (
IF( Beaconldentity = MyMACAddress )
/*
* Add the requester to the end of the BeaconList
*/
BeaconList[ NumberAssignedPrioritySlots ] = MAC address of requester;
NumberAssignedPrioritySlots = NumberAssignedPrioritySlots + 1;
4S _( RELEASE_PRIORITY SLOT CONTROL_FRAME ):
(
IF( Beaconldentity = MyMACAddress )
CA 02242985 1998-07-14
CA9 98 023 3~
IF( MAC address of requster found in the BeaconList = at index x)
BeaconList[ x ] = NULL Mac address;
/*
* This step does not have to be done every time a device
* releases a priority slot...
*/
Reorder BeaconList so all NULL MAC addresses at end of list.
NumberAssignedPrioritySlots = NumberAssignedPrioritySlots - 1;
IS }
}
Process Beacon
(
20 input: BeaconData
IF( Beaconldentity = NULL )
(
25 Beaconldentity = source MAC address of the Beacon;
IF( MyMACAddress == Beacon identity )
(
30 /*
* This device is generating and receiving beacons. This is not permitted.
* Stop sending beacons if the device heard has a numerically smaller MAC
address.
*/
IF( MyMACAddress > source MAC address of the Beacon )
/*
* In this simple implementation, beacon generation by this device is simply
stopped.
* The process of Establishing athe Presence of a Beacon Generator in the Cell
* will be followed to establish new beacon generators) instead of sending a
special
* MAC control frame informing all devices in the BeaconList of the identity of
the new
* beacon generator.
*1
MyPrioritySlot = 0;
Beaconldentity = source address of the Beacon;
inform the upper layer that the priority slot is no longer available (it will
be re-requested if still
needed).
CA 02242985 1998-07-14
CA9 98 023 38
IF( source MAC address of the Beacon == Beaconldentity )
IF( MyMACAddress is in the BeaconData )
{
MyPrioritySlot = ordinal position of MyMACAddress in the BeaconData
if( MyPrior itySlot == 0 )
{
/'
* We have been passed responsibility of beacon generation
'/
I S Beaconldentity = MyMACAddress;
BeaconList = BeaconData;
ELSE
{
/*
' Cancel any pending transmit and submit priority traffic instead.
*/
Send_Frame_Routine( NON PRIORITY_DATA,
dequeue upto NPAT of non priority data from non-priority data queue);
)
l
ELSE
{
/*
* We have lost the use of our priority slot. Since this implementation does
not use split
* beacons this should only occur as a result of a release priority slot
request. In the case
* where the release priorty slot request was issued but not honoured by the
beacon generator,
* it is assumed that the upper layer will timeout on the request confirmation
and resubmit it.
*/
inform upper layer that the priority slot is no longer available.
/*
' Note in this simple implementation the beacon generator always generates a
single beacon
' indicating the MAC addresses of all devices assigned priority slots.
*/
IF( MinimumContentionSlot < number of entries in Beacon Data )
{
MinimumContentionSlot = number of entries in BeaconData;
NumberAssignedPrioritySlots = MinimumContentionSlot;
ELSE
CA 02242985 1998-07-14
CA9 98 023 39
r
* This simple implementation does not inform beacon generators in overlapped
cells of the largest
number of allocated priority slots in the overlapped cells. Similarly this
implementation does not
$ ' require priority devices in the overlap to register with the beacon
generator using the numerically
higher MAC address. The processing for these (wireless) enhancements would be
performed here.
* However, we may need to increase the minimum contention slot value used if
this beacon generator has
more
* allocated priority slots.
>~
IF( MinimumContentionSlot c number of entries in Beacon Data )
MinimumContentionSlot = number of entries in BeaconData;
)
NumberAssignedPrioritySlots = MinimumContentionSlot;
Pseudo Code For the Second Aspect of the Invention
Pseudo code is not shown for the operation of the subordinate modulation
physical
layer or the subordinate modulation MAC protocol layer since this operation is
unaffected by this invention.
Subordinate Modulation Protocol Manager Operation
(
CurrentModulation = CONTROLLING MODULATION;
When requested to transmit data by the subordinate modulate MAC protocol
layer:
IF( CurrentModulation == My_SUBORDINATE_MODULATION )
3S ELSE
)
send data to the subordinate modulation physical layer;
queue data for transmission to the subordinate modulation physical layer;
Upon receiving data from the subordinate modulation physical layer:
CA 02242985 1998-07-14
CA9 98 023 40
IF( CurrentModulation == My_SUBORDINATE MODULATION )
(
transfer received data to the subordinate modulation MAC protocol layer;
)
S ELSE
(
discard the data;
)
Upon receiving an indication of a modulation change from the link manager:
(
CurrentModulation = modulation indicated by the link manager;
IF( CurrentModulation == My_SUBORDINATE MODULATION )
t
send all queued subordinate modulation MAC protocol to the subordinate
modulation physical layer;
Upon determining that the subordinate modulation MAC protocol layer requires
access to the medium:
request the link manager to switch to My_SUBORDINATE MODULATION for a period
of time = MT;
l
Link Manager Operation
(
CurrentModulation = CONTROLLING_MODULATION;
When requested to change modulation to subordinate_modulation for time period
MT by a subordinate protocol manager:
IF( CurrentModulation != subordinate_modulation )
request the controlling modulation MAC protocol layer to generate a SOD frame
using(
subordinate_modulation and MT );
Upon indication from the controlling modulation MAC protocol that the current
modulation is Modulation:
(
CurrentModulation = Modulation
Indicate current modulation to all protocol managers;
)
)
CA 02242985 1998-07-14
CA9 98 023 41
Controlling_Modulation MAC_Protocol Operation
(
$ ' Only the operation of the MAC required in the context of this invention
are shown.
*/
CurrentModulation = CONTROLLING_MODULATION;
periodically generate jamming signals in all subordinate modulations;
PendingModulation = NULLL;
PendingModulationTime - 0;
When requested to send SOD frame for subordinate modulation = Modulation, and
time = MT
1$ IF( PendingModulation = NULL ) AND ( CurrentModulation =
CONTROLLING_MODULATION )
(
PendingModulation = modulation;
PendingModulationTime = MT;
Send_SOD_Frame( modulation, MT );
ELSE
(
queue modulation change request;
)
When SOD frame indicated as transmitted:
(
CurrentModulation = PendingModulation;
PendingModulation = NULL;
Stop generating jamming signals in current modulation;
set ModulationTimer to expire in MT;
Indicate CurrentModulation to Link Manager;
When Modulation Timer expires:
(
resume periodically generating jamming signals in CurrentModulation;
CurrentModulation = CONTROLLING_MODULATION;
Indicate CurrentModulation to Link Manager;
IF( queued modulation change requests )
dequeue modulation change;
CA 02242985 1998-07-14
CA9 98 023 42
PendingModulation = modulation;
PendingModulationTime = MT;
Send SOD_Frame( modulation, MT );
Controlling_Modulation_Physical_Layer Operation:
(
/*
* Only the operation of the physical layer required in the context of this
invention are shown.
*/
IS
When requested to generate jamming signal in modulation=Modulation
generate jamming signal in modulation;
)
