Patent Publication Number: US-5422885-A

Title: Contention free local area network

Description:
TECHNICAL FIELD 
     This invention relates generally to the field of local area networks (LANs) and more specifically to a system and method for providing contention free transmission of messages. 
     BACKGROUND 
     Conventional local area networks come in two primary configurations, ring and multi-drop configurations. In a ring configuration, messages are passed from one node in the network to the next until they reach their destinations. Since a given node transmits a message directly to only the next node in the ring network, there is no possibility of message contention (collision) on a given internodal link. The drawback of the ring configuration is that not all nodes on the network can listen to a transmitted message simultaneously (i.e., it is not possible to &#34;broadcast&#34; the message to several nodes at any one given time). 
     In a multi-drop configuration, a single hardware bus unites all the nodes together. This allows the message transmitted by a single node to be received by all the other nodes simultaneously, a desirable feature in many real-time applications (e.g., such as in radio frequency communication systems which require messages to be sent to several repeaters in the system at approximately the same time). The drawback to this configuration, however, is that it is entirely possible for two or more nodes in the network to transmit a message simultaneously, causing message contention (collision) which results in corruption of the transmitted messages. 
     Other fairly elaborate LAN protocols, such as Carrier Sense Multiple Access (CSMA, such as found in Ethernet), Token Bus (involving passing a token in a message frame), and Arbitration by Master, among others, have been developed to minimize the contention that could occur on the LAN buses. The problem with most of these more sophisticated protocol networks is that they involve using expensive circuitry and IC&#39;s (such is the case with Ethernet and Token Bus configurations), or relatively complex software (such as with Arbitration by Master configurations) which result in expensive networks and/or long handshaking delays. 
     Presently, several types of local area networks are used in communication networks, with some of the more frequently used LANs being the Ethernet, Token Bus, LocalTalk and Token Ring networks. The Ethernet LAN uses a multi-drop configuration which employs a carrier sense multiple access contention scheme (CSMA) which minimizes collisions on the bus. Ethernet has a drawback in that it does not eliminate collisions entirely, something which is not acceptable in many communication systems. Ethernet systems typically employ a two conductor cable for operation. The Token Bus network is also a multi-drop network, the Token Bus however employs message embedded token passing to avoid collisions on the bus. Token Bus networks also employ two conductor cables, but require sophisticated electronics and software to implement the embedded token passing scheme. 
     The LocalTalk network is also configured as a multi-drop system but employs a software handshake protocol between the message source node and the destination node. LocalTalk networks require sophisticated software to implement the handshake routines. These handshakes reduce the maximum effective information transfer rate for the network. Finally, Token Ring networks avoid all contentions between communication nodes wanting to transmit messages at the same time by passing a token from node to node. However, the Token Ring network is not able to support broadcasting of messages to more then one node at a given time, a major drawback to systems which require messages to be sent to several nodes at one time. 
     A need thus exists for a contention free local area network which can be implemented without using complex hardware and/or software, which adds considerable cost to a communication system. The local area network should also be transparent to software and provide for high network utilization. The LAN should also allow for network efficiency not to be compromised when the network has a large number of nodes, and allow for the broadcasting of messages to more than one node at any given time. 
     SUMMARY OF THE INVENTION 
     Briefly, according to the invention, a method of transmitting a message in a communication network having a plurality of communication nodes comprises the steps of: determining if a transmit-enable token has been received at a control bus that is coupled to the communication node requesting to transmit the message; transmitting the message via a data bus which is coupled to the plurality of communication nodes, once the transmit-enable token has been received; and sending the transmit-enable token via the control bus to the next communication node, 
     In another aspect of the invention, a communication system comprises a plurality of repeaters and a data bus coupled to the plurality of repeaters for allowing messages to be transmitted among the plurality of repeaters. The communication system further comprises a control bus coupled in a daisy-chain arrangement to the plurality of repeaters for allowing a token to be passed among the plurality of repeaters which is used to determine which of the repeaters can transmit a message via the data bus. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a diagram showing the basic architecture of a contention-free token passing network in accordance with the present invention. 
     FIG. 2 is a timing diagram showing tokens and request-to-send signals in accordance with the present invention. 
     FIG. 3 is a diagram of a communication system in accordance with the present invention. 
     FIG. 4 is a flowchart illustrating the typical operation sequence for a typical communication node in accordance with the present invention. 
     FIG. 5 is a preferred embodiment of a control circuit which provides contention-free data bus arbitration in accordance with the present invention. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     Referring now to the drawings and specifically to FIG. 1, there is shown a block diagram of a communication system 100 which utilizes a token passing control bus and a multi-drop data bus in accordance with the present invention. System 100 consists of two separate types of communication links, a multi-drop bus 104 for the transport of data, and a daisy-chain ring control bus 102 for the transport of transmit-enable tokens. Daisy-chain ring 102 comprises sections 110, 124, 126, 128, 130 and 122. In the preferred embodiment, the network nodes 108, 112, 114, 116, 118 and 120, are preferably radio frequency repeaters such as those utilized in trunked radio frequency communication systems. Each of the repeaters includes a transmitter and receiver section for relaying radio frequency information. System 100 can have more than or fewer than the number of nodes shown, if desired. 
     Each of the individual nodes is linked to the multi-drop bus 104 via individual bus extensions 106. Multi-drop bus 104 preferably utilizes a serial bus architecture, although a parallel bus architecture could also be used if higher data transmission speeds are required. 
     Repeaters 108, 112, 114, 116, 118, and 120 communicate with each other in order to coordinate communication activity in the system. The repeaters pass a token via daisy-chain ring 102 in order to provide for contention-free communications among the repeaters. A &#34;token&#34; is nothing more than a positive voltage edge (e.g., a logic &#34;0&#34; to a logic &#34;1&#34; transition) on the inbound token passing link of a particular node. For example, communication link (T1) 110, is the inbound token passing link for node 112, while link (T2) 124 is the outbound token passing link for node 112. Control bus 102 is a uni-directional bus with the transmitenable token being passed among the repeaters in one direction of travel. Each of the repeaters receives the token via its inbound token passing link and generates a token which is sent via the repeater&#39;s outbound token passing link. The control of the token is controlled by a control means or control section 132 which is found in each of the repeaters. The control section will be discussed in detail later. The timing and operating scheme of the tokens may be best understood by looking at the timing diagram of FIG. 2. 
     In FIG. 2, when a particular node such as repeater #2 shown on FIG. 1, receives a positive voltage edge (e.g., from a zero voltage level state to a 5 volt level state) on its inbound token passing link T1, it changes the state of its outbound token passing link T2, from a logical &#34;1&#34; to a logical &#34;0.&#34; This is shown in FIG. 2 by the positive voltage level in line T1 (202) and then looking at the outbound line T2 for node #2, where the voltage on line 204 goes from a &#34;high&#34; to a &#34;low&#34; level. 
     Line T1 (202) in FIG. 2, illustrates the logic levels present on inbound link 110 of node #2, while line T2 (204)illustrates the logic levels present on node #2&#39;s outbound token passing link T2. Each of the other lines of FIG. 2 show the logic levels present at their respective links (e.g., T3-TN). 
     After node #2 (112) changes its outbound token passing link logic level T2 (204) from a low logic level &#34;0&#34; to a high logic level &#34;1&#34;, node #3 (114) gets its cue to change the logic on its outbound link T3 (206) from a logical &#34;1&#34; voltage level to a logical &#34;0.&#34; This sequence of events continues throughout all of the remaining nodes in the network allowing for the token to be passed successively from node to node in a circular fashion (e.g., from node #1 to node #2, etc.). 
     In the preferred embodiment a logic level of &#34;1&#34; (or second voltage state) can equal a level of approximately 5 volts while a logical &#34;0&#34; level (or first voltage state) can be a voltage level of approximately 0 volts. Different voltages can be utilized depending on the system being designed. For example, a voltage range from 0 to 1.5 volts can signify a low voltage, while a voltage range from 3.5 to 5 volts can signify a high voltage level. 
     In the case that a particular communication node wishes to transmit a message when it receives the token, it keeps its outbound token passing link logic level at a high logic level for as long as it is transmitting a message (e.g., for node #2, the period between the time it begins transmission at line 226 and end transmission at line 228, at which point it asserts its outbound link T3 voltage at a low logic level). If a node receives the transmitenable token and it does not wish to transmit a message, the node places a low logic level on its outbound communication link a very short time (approximately one bit time) after receiving a positive voltage edge on its inbound token passing link, causing the token to be passed to the next node in the control bus. Thus, a node keeps a token to itself only while transmitting a message. 
     An example will help in clarifying the above situation. If nodes #5 (118) and node #2 (112) both want to transmit messages, nodes #5 and #2 signal their intentions to transmit messages, by lowering the logic levels on their respective RTS (request-to-send lines)lines shown by lines 214 and 216 respectively. Each of the repeaters preferably assert their RTS lines at a random time after determining that they need to transmit a message. By randomizing the time the RTS line is asserted low at each of the repeaters, allows for each repeater to get an equal opportunity of being the first to gather access to the token which is circulating the system via control bus 102. Line 214 in FIG. 2, shows the logic level at the RTS terminal for repeater #5 while line 216 shows the voltage level for the RTS terminal for repeater #2. Lines RTS1, RTS3, RTS4 and RTSN are all shown at a logic &#34;1&#34; indicating they are not requesting to transmit. 
     In this particular example, node (repeater) #5 is the first to receive the inbound token as shown by line number 218. Upon receipt of the inbound token from node #4 (shown by line 222), node #5 asserts its outbound token passing line low and begins transmitting a message on the multi-drop data bus 104 shown on FIG. 1. The outbound token also serves as the CTS (clear-to-send) line which enables the start of the message frame by node #5. Upon completion of the message as shown by the intersection of line number 224 and line 210, node #5 negates its RTS line (brings it back to a logic high &#34;1&#34; state, shown in line 214), which triggers the negation of the outbound token, shown by the shift from logic &#34;1&#34; to logic &#34;0&#34; in TN line 212. 
     The token has now been passed to node #N. Since node #N has nothing to transmit (its RTS line is at a logical &#34;1&#34;, not shown), it passes its token to node #1 within a very short time. Node #1, in turn passes the token to node #2. Since node #2 does wish to transmit a message (its RTS line 216 is at a logic low), it holds on to the token until it has completed transmission, shown by line 226. At which point it negates its RTS line, and returns the voltage level on the outbound token passing link to a logic &#34;0&#34; level, shown by the shift in voltage level in line 206 at the point that node #2 completes transmission at line 228. 
     Under the above mentioned scheme, only one node in the network may possess a token at a given time. This allows only that one node transmits at any one point in time, thereby avoiding bus contention problems completely. 
     In FIG. 3, a communication system 300 utilizing a set of repeaters 304, 314 and 306 coupled together via a contention-free LAN as described above is shown. The LAN consists of a multi-drop bus 310 for the transport of data, and a daisy-chain ring 312 for the transport of tokens as previously discussed. Each of the repeaters is in communication to a trunked central controller 308 which controls the operation of repeaters 304, 314 and 306. The communication system also includes a set of subscriber radios 302 which can communicate with each other via one of the repeaters 304, 314, and 306. Preferably, communication system 300 is a trunked communication system as known in the art, with the addition of a contention-free LAN as described by the present invention. 
     The LAN network linking repeaters 304, 314 and 306 and system central controller 308 allows the communication units to stay in contention-free communication with each other. 
     In FIG. 4, a flowchart 400 showing the steps that are executed for contention-free transmission is shown. In step 402, the communication node is in an idle condition, given that the RTS line is at a logic &#34;1&#34; or high voltage level. The communication node then determines in step 404 there is a low logic level (&#34;0&#34;) on its inbound token passing link. If the inbound token signal is high, the routine keeps waiting in step 404. If the inbound signal is at a low level, the routine moves on to step 406. In step 406, the node determines if their is a positive voltage edge on the inbound token signal (e.g., that the voltage level has changed from a &#34;0&#34; logic level to a &#34;1&#34; logic level). If the inbound token signal has a positive edge, the routine moves to step 408. In step 408, the communication node asserts the outbound token signal and makes it a logical &#34;0.&#34; 
     In step 410, the decision is made whether the communication node is requesting to transmit a message via the data bus (RTS line asserted to a low logic level). If the communication node does not have a message to transmit (RTS is still at a high logic level) in step 414, the token is sent to the next communication node which is coupled to the control bus after a short pause (approximately equaling one clock cycle). The token is then sent to the next communication node by changing the voltage level on the communication node&#39;s outbound token passing link from a low to a high logic level. If in step 410, the communication has asserted its RTS line low, the communication node begins transmission of its message in step 418. In step 416, the RTS line is checked to determine if the message has finished being transmitted (RTS logic level changed from a low to a high logic level). If the RTS line has been de-asserted, the token is sent to the next communication node in step 412 by changing the voltage level on the outbound token passing link from a low to a high logic level. 
     In FIG. 5, a simplified schematic of a control circuit 500 for implementing the data bus arbitration process discussed above is shown. Circuit 500 is part of the communication nodes control means. Inputs to the data bus arbitration circuit include input &#34;TI&#34; 502, which is the voltage input from the communication nodes input token passing link (the input from the preceding node in the daisy-chain arrangement) and the RTS 504 input terminal which is coupled to a standard control line coming from the communication node (repeater) which informs circuit 500 that the repeater has a message to transmit. 
     In this particular embodiment, whenever the RTS line 504 is a logic &#34;0&#34; it indicates to control circuit 500 that the repeater wants to transmit a message. The final input to the circuit is a clock signal terminal 506 which is coupled to the repeater&#39;s internal clock circuitry in order to synchronize circuit 500 with the rest of the repeater&#39;s circuit. Output terminal TO 508 of circuit 500 provides the outbound token signal via the output token passing link to the next communication node (repeater) coupled to control bus 102 (e.g., assuming we are making reference to repeater #2 in FIG. 1, TI terminal 502 would be coupled to the output terminal TO of repeater #1 (108) while the output terminal TO 508 of node #2 would be coupled to the input terminal TI of repeater #3). The output token signal provided by output terminal TO 508 acts as the clear-to-send (CTS) signal to the next repeater coupled to control bus 102 informing the repeater that the token is now in its possession, allowing the next repeater to transmit a message if it cares to do so. 
     Each of the repeaters preferably also include a simple hardware relay feature (not shown) which will bypass circuit 500 and allow the token from the preceding node to be sent to the next node in the control bus if a node (repeater) becomes inoperative. This can simple take the form of a hardware circuit such as a relay circuit which links input TI 502 with output TO 508 in the case of a malfunction condition at a particular repeater. This would in effect cause the particular malfunctioning repeater to be bypassed in the control bus token passing sequence. 
     In communication systems such as the communication system previously discussed, the present invention allows for system software overhead to be minimized, since the handling of contention-free message transmissions between repeaters is simplified. This is especially important in communication systems having a large number of repeaters (e.g., over 10 repeaters). 
     Although the present invention has been shown implemented in a radio frequency system having several repeaters, the communication network of the present invention can also be utilized in other systems which require contention free communications. For example, the present invention can be utilized for linking computers and workstations together, in connecting system or backplane modules together which require effective communications, and other similar communication applications. In existing systems which are presently utilizing multi-drop buses for communications the described invention allows for a cost effective retrofit for providing contention-free communications. 
     In summary the present invention combines the advantages of ring and multi-drop local area networks in one configuration without suffering the disadvantages of either (e.g., such as the inability to broadcast with ring networks and the contention problems associated with multi-drop networks). The invention can be implemented with a simple and inexpensive hardware mechanism to eliminate contention. The invention also guarantees that dead time between consecutive messages remains less than (N-1) bit times, where &#34;N&#34; is the total number of communication nodes on the network. In practice, dead times will be significantly less than N-1 bit times, particularly when N is a large number (e.g., over 20).