System for adaptive backoff mechanisms in CSMA/CD networks

A system for controlling traffic on a contention-based local area network (LAN) such as one according to the CSMA/CD or Ethernet specification. To selectively preempt low priority messages on the LAN so that high priority messages may be transmitted, the system uses a station profile table (260) that holds information relating to an average frame length for messages transmitted from each station on the LAN. When a station connected to the LAN through a network interface (250) needs to transmit a high priority message such as a voice communication, a traffic monitor (240) checks for a low priority message on the LAN. If a low priority message is detected, a station identifier, priority level, and length of frame already transmitted are determined, and an average frame length is read from the station profile table (260). If the length of frame already transmitted is less than a predetermined threshold, then a computing element (220) transmits the high priority message through the network interface (250) to the LAN, to force a collision. After waiting for a period shorter than the standard backoff period defined by the CSMA/CD specification, the high priority message is retransmitted.

FIELD OF THE INVENTION 
This invention relates to the field of data communications, and more 
particularly, to local area networks that use a CSMA/CD bus access scheme. 
BACKGROUND OF THE INVENTION 
Local area networks (LANs) are networks interconnecting terminals, 
computers, work stations, and other intelligent systems within a building 
or a small number of buildings on a campus. LANs may be created using 
several different network topologies, but a commonly used one is a bus, in 
which all stations are connected to the same cable. By transmitting data 
on the bus, any two or more stations are able to communicate. 
Standards for local area networks have been developed by the IEEE 
(Institute of Electrical and Electronics Engineers) through its committee 
802 on local networking. One of the more popular standards for local area 
networks is IEEE standard 802.3 that defines a CSMA/CD (Carrier-Sense 
Multiple-Access/Collision Detect) bus, an example of which is the Ethernet 
specification. The basic concept underlying a CSMA/CD protocol is that all 
stations in the LAN listen for transmissions on the bus. When a station 
needs to transmit a message, it does so only when it detects that no other 
stations are transmitting. This is known as carrier sensing. However, 
since a number of stations exist on the LAN, collisions may still occur. 
Because stations are physically displaced from one another, two or more 
stations may concurrently sense that the no station is transmitting on the 
bus and begin transmitting, thereby causing a collision. When stations 
detect a collision, they transmit a special jam signal to notify all other 
stations of the collision and to abort their transmissions. After waiting 
for a backoff period as defined in the CSMA/CD specification, the stations 
may retransmit their messages. Due to the differing physical locations of 
the stations on the bus and propagation delays that occur for signals 
transmitted on the network bus, the jam signal will be detected at 
different times. Therefore, transmissions will be aborted at different 
times and retransmissions will be attempted after a backoff period, 
thereby avoiding another collision. 
In addition to text and data messages, a LAN may also carry messages 
comprising real-time voice and/or video signals. These are high priority 
messages, comprising sequences of short frames, which in the conventional 
CSMA/CD environment, may be forced to wait behind long, low priority, 
message frames thereby resulting in a halting presentation, and generally 
undesirable results. 
One prior art solution to this problem is to allow users to transmit high 
priority information regardless of whether a carrier signal from any other 
stations is present. Using this scheme, when a high priority user desires 
to transmit a message, the high priority user forces a collision on the 
line. When the collision is detected, and the transmissions aborted, the 
high priority user uses a shorter backoff time than the one agreed upon in 
the CSMA/CD standard, effectively bumping low priority traffic in all 
cases. However, this method works properly only when the network 
utilization is low. When loads are heavy, the low priority messages might 
never complete their transmissions from constantly being bumped by higher 
priority messages. 
SUMMARY OF THE INVENTION 
The present invention provides a modification to the CSMA/CD protocol, or 
any other contention-based local area network (LAN) protocol, that 
provides a more efficient allocation of network resources. 
In accordance with the present invention, a system is provided to monitor 
the traffic of the network. Specifically, two main parameters are 
monitored: the lengths of the transmitted frames; and the number of bytes 
from the current frame that have already been transmitted to the network. 
The monitored parameters are then analyzed by a computing element to 
determine whether or not a collision is to be forced. 
When there is a heavy load on the network, high priority messages such as 
real-time voice communication signals which are typically transmitted in 
66-byte frames, may be forced to wait behind low priority text or data 
messages made up of long frames of many hundreds of bytes. When loads are 
heavy, it is desirable to allow the computing element to force a collision 
and bump a frame only if relatively few bytes of the frame have been 
transmitted. If more then a predetermined number of bytes have already 
been transmitted, the high priority frame will wait until the low priority 
transmission is successfully completed in order to avoid having to 
retransmit a long frame. 
BRIEF DESCRIPTION OF THE DRAWINGS

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
The present invention is a system for use on contention-based local area 
networks (LANs) such as the CSMA/CD (Carrier-Sense 
Multiple-Access/Collision Detect) or Ethernet specifications. These 
specifications are industry-wide standards for local networking, and are 
considered well known to those of ordinary skill in the art of computer 
communications. An inventive data structure known as a station profile 
table is provided for use by the system to determine when a message on the 
LAN should be pre-empted in order to transmit a higher priority message. 
As shown in FIG. 1, a system according to the present invention operates in 
the environment of a contention-based local area network (LAN). The 
network comprises a network bus 170 having terminators 110 and 160 at 
either end, and having a plurality of computer stations 120-150 connected 
thereto. In a preferred embodiment, the LAN is constructed in accordance 
with the CSMA/CD or Ethernet specifications. 
Referring to FIG. 2, a typical computer station 120 for use with the 
invention is a general purpose computing device in the form of a 
conventional personal computer, having a central processing unit (CPU) 
210, a system memory 230, a network interface 250 for connecting the 
station to the LAN, and other components not specifically shown in FIG. 2, 
such as a display, keyboard, mouse, etc. The network interface 250 will 
typically be implemented as a network interface card (NIC) in the computer 
station. As will be discussed in further detail below, the station 120 
additionally includes a computing element 220, a traffic monitor 240, and 
a station profile table 260. 
The traffic monitor 240 is used to monitor messages that are transmitted on 
the network bus. The traffic monitor preferably monitors such parameters 
as the length of message frames that are being transmitted on the network 
bus, an identifier of the station that is transmitting the message, and 
the priority level of the message. The traffic monitor may be implemented 
as hardware or software, either as part of the station itself or as part 
of a network interface card NIC). 
The station profile table 260 is a data structure that is stored in either 
the system memory 230 located on the station 120 itself, or in a memory 
(not shown) of a network interface 250, or any other computer-readable 
medium, such as a magnetic disk, known in the art. An exemplary station 
profile table, as shown in Table 1 set forth below, includes fields for 
holding data representing an identifier of the station transmitting a 
message, the priority level of the message, and an average frame length 
for the message. In addition, the station profile table may optionally 
include a field for holding data representing a threshold value. 
TABLE 1 
______________________________________ 
Station Profile Table 
Station Priority Average Threshold 
Identifier 
Level Length (%) 
______________________________________ 
A High 75 50 
A Low 1500 80 
B High 100 50 
B Low 1000 80 
C High 66 50 
C Low 797 80 
______________________________________ 
Before the station 120 transmits a message on the network, the network 
interface determines whether the network is free and if not, the computing 
element 220 determines whether the message currently being transmitted 
should be preempted. As will be explained in connection with FIG. 4, the 
computing element 220 analyzes the parameters that are monitored by the 
traffic monitor, and compares the parameters with information from the 
station profile table. When appropriate, the computing element transmits a 
message through the network interface to force a collision. As an 
alternative to transmitting a message to cause a collision, then waiting 
for the collision to be detected and a subsequent jam signal to be 
transmitted in order to abort a transmission, the computing element could 
simply transmit the jam signal to cause the message on the LAN to be 
aborted. The computing element may be implemented as hardware or software 
that is controlled by a processor within the network interface 250. 
Alternatively, the program code can be software that is executed by the 
CPU 210. 
FIG. 3 is a flow chart depicting an operation of the system according to 
the present invention to maintain a station profile table. At a step 310, 
the data structure for the station profile table is created. As discussed 
above, the data structure is preferably a table that includes fields for 
holding data representing information concerning stations that are 
currently transmitting on the LAN. The data preferably includes a network 
address of each currently transmitting station, which is typically 
represented as a 48-bit number, a priority level, an average frame length, 
and, optionally, a threshold value. 
Station profile tables may be maintained on each station connected to the 
network, or on only a single station. Where a single station profile table 
is maintained on a single station, the other stations still keep copies of 
the station profile table, but updating of the table is only done on the 
single station, and the updated information is transmitted to each of the 
other stations on the network. 
The traffic monitor 240 monitors the messages on the network bus 170 at a 
step 320, and collects the station identification, priority level, and 
frame length information for each message transmitted. For each message of 
a given priority level that is transmitted by a particular station, an 
average frame length is computed at a step 330. As a frame completes 
transmission across the LAN, its length becomes known. The average frame 
length will then be calculated as a running average, where the mean frame 
length is recalculated as each successive frame completes transmission. 
The station profile table is then updated with the computed average frame 
length at a step 340. This process repeats by returning to the step 320 as 
long as messages are being transmitted on the LAN. Since the process of 
maintaining the station profile table is continuous, the steps shown in 
FIG. 3 are preferably executed in the background operation of the station 
120. 
Referring to FIG. 4, a process for using the station profile table to 
control message traffic on the network bus executes concurrently with the 
table maintenance operation. 
When a station has a high priority message to transmit, the network 
interface of the station first detects if another message is being 
transmitted on the network at a step 410. If so, an identification of the 
station currently transmitting the message is determined by the traffic 
monitor at a step 420. At a step 430, the traffic monitor of the station 
desiring to transmit the high priority message determines the priority 
level of the message on the network bus 170. 
If, at a step 435, the priority level of the message to be transmitted is 
lower than the priority level of the message currently being transmitted, 
the message to be transmitted waits, at step 437, for the current message 
to finish transmitting. 
If, at a step 435, the priority level of the message to be transmitted is 
higher than the priority level of the message currently being transmitted, 
then, at a step 440, the station identifier and priority level of the 
message are used to look up an average frame length from the station 
profile table. The traffic monitor of the station desiring to transmit a 
message then determines how much of a frame has already been transmitted 
at a step 450. This is preferably measured in terms of a number of bytes. 
The traffic monitor then determines if the portion of the frame that has 
already been transmitted is less than a predetermined threshold at a step 
460. If the portion of the frame that has already been transmitted is 
greater than a predetermined threshold, the message to be transmitted 
waits, at step 470, for the current message to finish transmitting. 
If the portion of the frame that has already been transmitted is less than 
a predetermined threshold, then the computing element 220 will begin 
transmitting the higher priority message to thereby force a collision at a 
step 480. As discussed above, instead of transmitting the high priority 
message, the computing element could alternatively send a jam signal to 
cause the low priority message to be aborted. 
In order to insure that the higher priority message is transmitted before 
the lower priority message, the station with the high priority message 
waits for a shorter backoff period than the minimum backoff period that is 
defined by the CSMA/CD standard. After the shortened backoff period has 
elapsed, the high priority message is retransmitted. The shortened backoff 
period may be any length of time shorter than the agreed-upon period, and 
may be stored as a parameter on each station or as a parameter in the 
station profile table. The shorter backoff period may be implemented as a 
single global parameter or may be tailored to each station and/or each 
message priority level. In a preferred embodiment, the passage of time is 
monitored by the traffic monitor 240 using timing signals from the bus 
170, but could alternatively be implemented using the CPU 210 having 
either a software or hardware clock (not shown), or any other timing 
mechanisms known in the art. 
As noted above, if, at a step 460, it was determined that the portion of 
the frame already transmitted was not less than the threshold, then the 
station wanting to transmit the high priority message waits for the 
transmission of the lower priority frame to complete at a step 470. This 
aspect of the present invention is especially useful for improving the 
efficiency of network usage. For instance, referring again to Table 1, 
assume that Station A has already transmitted 1490 bytes of a low priority 
message. As seen in Table 1, the average frame length for low priority 
messages sent by Station A is 1500 bytes, the maximum length defined in 
the Ethernet specification. If a high priority message from Station C, 
having an average frame length of only 66 bytes, were allowed to bump 
Station A's low priority message, network resources would be wasted since 
Station A would have to retransmit the entire frame. Therefore, the time 
spent in retransmitting the 1490 bytes that were previously transmitted 
would have been wasted. With the present invention, the computing element 
determines that the 1490 bytes that have already transmitted represent a 
higher percentage of the average frame length than the 80% threshold set 
forth in the station profile table, and forces the higher priority message 
to wait for the remaining 10 bytes to transmit. 
Threshold values may be stored as either a global parameter, applicable to 
all messages of all stations, or may be stored in the station profile 
table, allowing the fine tuning of threshold values for each priority 
level message from each station. 
In alternative embodiments of the present invention, the steps of 
determining a station identifier, determining a priority level, 
determining an average frame length, and determining a length of frame 
already transmitted occur in various different orders, and may take place 
concurrently. 
As can be seen from the above descriptions, the present invention provides 
better allocation of network resources while simultaneously allowing 
higher priority message to be transmitted before lower priority messages.