Abstract:
A method for arbitrating access to a time slot in a time division multiple access network in an asynchronous hub with a bus guardian is provided. The method including receiving signals from competing nodes claiming access to the same time slot at the bus guardian of the asynchronous hub, selecting one of the nodes based on a priority scheme, and relaying a message from the selected node and blocking the message from the non-selected node.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS  
       [0001]     This application is related to and claims the benefit of the filing date of the following U.S. Provisional Applications: 
        Ser. No. 60/523,782, entitled “HUB WITH INDEPENDENT TIME SYNCHRONIZATION” filed on Nov. 19, 2003,     Ser. No. 60/523,900, entitled “COMMUNICATION FAULT CONTAINMENT VIA INDIRECT DETECTION,” filed on Nov. 19, 2003, (the &#39;900 Application)     Ser. No. 60/560,323 entitled MESSAGE AUTHENTICATION IN A COMMUNICATION NETWORK and filed on Apr. 6, 2004 (the &#39;323 application)     Ser. No. 60/523,785, entitled “PRIORITY BASED ARBITRATION FOR TDMA SCHEDULE ENFORCEMENT IN A DUAL CHANNEL SYSTEM” filed on Nov. 19, 2003 (the &#39;785 application).        
 
         [0006]     These provisional applications are incorporated herein by reference.  
         [0007]     This application is also related to the following co-pending, non-provisional applications:  
         [0008]     Attorney docket no. H0004947, entitled “COMMUNICATION FAULT CONTAINMENT VIA INDIRECT DETECTION,” filed on even date herewith (the &#39;947 Application).  
         [0009]     Attorney docket no. H0007587 entitled “PORT DRIVEN AUTHENTICATION IN A NETWORK” filed on even date herewith (the &#39;587 Application).  
         [0010]     Attorney docket no. H0005459 (400.010US01) entitled “PRIORITY BASED ARBITRATION FOR TDMA SCHEDULE ENFORCEMENT IN A MULTI-CHANNEL SYSTEM” filed on even date herewith (the &#39;459 application).  
         [0011]     These non-provisional applications are incorporated herein by reference. 
     
    
     BACKGROUND  
       [0012]     Communication networks are used in a variety of applications including telephone and computer systems, weapons systems, navigational systems, and advanced control systems in cars, aircraft and other complex systems. Given the variety of applications, many kinds of communications networks have been developed over the years. One common characteristic of communication networks is the use of a communication medium that interconnects various nodes on the network. Various topologies and protocols have been developed to control communications between the nodes of these networks.  
         [0013]     One type of network is referred to as Time Division Multiple Access (TDMA). In a TDMA network, nodes in the network are assigned time slots for communicating over the network. Many different TDMA protocols have been developed for communication between nodes of a network. For example, these protocols include TTP/C, SAFEbus, FlexRay and other TDMA protocols.  
         [0014]     In many time-triggered protocols, a global clock synchronization protocol is used to maintain synchronization between the clocks at each of the nodes. This synchronization of the local clocks assures that the nodes have the same time basis for determining the beginning of each time slot. Each node monitors the transmission on the network and independently synchronizes its clock to the global clock of the network based on the timing of the receipt of selected signals from the other nodes, e.g., an action time signal in the TTP/C Specification.  
         [0015]     One problem with existing time-triggered protocols with global time synchronization is that faults that propagate in the network may adversely affect the time synchronization of nodes in the network. When a node transmits out of turn, if the frame or message is allowed to reach other nodes in the system, then the global synchronization may be adversely impacted.  
         [0016]     Therefore, a need exists for an improved mechanism for reducing the impact of faults on a global time synchronization in a network implementing a time-triggered protocol.  
       SUMMARY  
       [0017]     Embodiments of the present invention provide an asynchronous bus guardian for a time division multiple access (TDMA) network. The guardian implements an arbitration technique to select between nodes that claim access to the same time slot to mitigate the propagation of faults in the network.  
         [0018]     In one embodiment, a method for arbitrating access to a time slot in a time division multiple access network in an asynchronous hub with a bus guardian is provided. The method including receiving signals from competing nodes claiming access to the same time slot at the bus guardian of the asynchronous hub, selecting one of the nodes based on a priority scheme, and relaying a message from the selected node and blocking the message from the non-selected node. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0019]      FIG. 1  is a block diagram of one embodiment of a star network that implements a distributed, time-triggered protocol with a hub that operates with independent time synchronization.  
         [0020]      FIG. 2  is a block diagram of another embodiment of a star network in an electronic system.  
         [0021]      FIG. 3  is a flow chart of one embodiment of a process for a bus guardian in an asynchronous hub for controlling relaying messages from nodes during time slots in a TDMA network.  
         [0022]      FIG. 4  is a flow chart of one embodiment of a process for a node for determining a proper data frame among different data frames received on different channels in a TDMA network. 
     
    
     DETAILED DESCRIPTION  
       [0023]     In the following detailed description, reference is made to the accompanying drawings that form a part hereof, and in which is shown by way of illustration specific illustrative embodiments in which the invention may be practiced. These embodiments are described in sufficient detail to enable those skilled in the art to practice the invention, and it is to be understood that other embodiments may be utilized and that logical, mechanical and electrical changes may be made without departing from the spirit and scope of the present invention. The following detailed description is, therefore, not to be taken in a limiting sense.  
         [0024]     Embodiments of the present invention provide a network with an asynchronous hub. In this network, a fault occurs, for example, when a node attempts to transmit during a timeslot assigned to another node. When the fault occurs, a bus guardian in the asynchronous hub uses an arbitration technique to assure that the message from the node assigned to the time slot is transmitted from the hub to its destination. Advantageously, this technique uses indirect detection to detect the fault with the attempt to transmit during the wrong time slot. The indirect detection aspect of the invention is described in more detail in the &#39;947 and &#39;900 applications incorporated by reference above.  
         [0025]      FIG. 1  is one embodiment of a network indicated generally at  100 . Network  100  includes asynchronous hubs  102  and  104  connected in a star configuration with nodes  106 - 1  to  106 -N. Hubs  102  and  104  are referred to collectively as “the hub” of network  100 . In this embodiment, network  100  includes two channels of communication for each node  106 - 1  to  106 -N. Hub  102  provides the first communication channel between the nodes  106 - 1  to  106 -N. Hub  104  provides the second communication channel between the nodes  106 - 1  to  106 -N. Data is transmitted as messages, e.g., frames, from one node to another in the network  100 . Each node transmits each frame to both of hubs  102  and  104 . Hubs  102  and  104  then selectively transmit the frames to the other nodes to provide 1:N communication for each node. Hubs  102  and  104  are asynchronous in that the hubs are not synchronized with the time base of the nodes  106 - 1  to  106 -N.  
         [0026]     In one embodiment, the network  100  implements a distributed, time-triggered communication protocol. For example, in one embodiment, the time-triggered protocol TTP/C described in the TTP specification Edition 1.0.0 of Jul. 4, 2002 issued by TTTech is used (the TTP/C Standard). In this protocol, each node  106 - 1  to  106 -N maintains synchronization with a virtual clock. In other embodiments, the nodes maintain time synchronization using other techniques.  
         [0027]     The nodes  106 - 1  to  106 -N are assigned time slots to use for transmission. In one embodiment, the nodes  106 - 1  to  106 -N transmit a signal “Clear To Send” (CTS) to the hubs  102  and  104  prior to the node&#39;s assigned time slot. This alerts the hub to expect data from the node. In one embodiment, the CTS signal is sent over the same communication medium as other messages exchanged between the node and the hub. In other embodiments, the CTS signal is sent over a different communication medium.  
         [0028]     Hubs  102  and  104  include bus guardians  110  and  112 , respectively. Bus guardians  110  and  112  perform an arbitration function for hubs  102  and  104  to deal with competing claims to the same time slot. In one embodiment, guardians  110  and  112  use priority schemes to select among the competing claims to a common time slot. In one embodiment, the guardians  110  and  112  implement complementary priority schemes so that the message from each competing node is relayed by at least one of the hubs  102  and  104 .  
         [0029]     In operation, hubs  102  and  104  assure that frames of data transmitted from one node to another arrive at the proper destination despite faults that occur in the network from time to time. Each node  106 - 1  to  106 -N is assigned a time slot to transmit frames in the network  100 . When a node  106 - 1  to  106 -N transmits a frame, the hubs  102  and  104  forward the frame to the other nodes on the network  100 . The intended destination node receives the frame as do all other nodes on the network  100 . The destination node processes the frame by determining, based on, e.g., a destination address in the frame, that the frame is destined for the node.  
         [0030]     In the course of processing data, a fault may occur in that two of nodes  106 - 1  to  106 -N may attempt to transmit during the same time slot. Each node that intends to transmit during a time slot sends out a CTS signal to each of hubs  102  and  104 . In the event that a hub, e.g., hub  102 , receives CTS signals from two nodes for the same time slot, the hubs  102  and  104  implement a procedure to assure that the frame from the proper node is transmitted to the other nodes by the hubs  102  and  104 . In one embodiment, the two hubs  102  and  104  implement different priority schemes to assure that the proper message is relayed by the hubs to the other nodes. In one embodiment, the two hubs  102  and  104  use complementary priority schemes. Complementary priority schemes result in one of the two frames being transmitted by one hub and the other of the two frames being sent by the other hub. In this embodiment, the correct message is received by the destination node because each node  106 - 1  to  106 -N receives both messages. The nodes  106 - 1  to  106 -N are able to verify the correct message has been received based on, for example, the transmit order list stored in each node  106 - 1  to  106 -N. Advantageously, with this embodiment, the hubs  102  and  104  do not need to store the list of time slots for each node. An example of this embodiment is described in more detail below with respect to  FIG. 3 .  
         [0031]      FIG. 2  is a block diagram of a system indicated at  200  that uses a communication network  100  of the type describe above with respect to  FIG. 1 .  FIG. 2  further shows that the nodes  106 - 1  to  106 -N are connected to a number of electronic devices  208 - 1  to  208 -N, e.g., sensors, processors, actuators, controllers, input devices and the like that communicate messages over the network  100 .  
         [0032]      FIG. 3  is a flow chart of one embodiment of a process for a bus guardian in an asynchronous hub for controlling relaying messages over a communication channel from nodes during time slots in a TDMA network. For purposes of this specification, a channel in a TDMA network includes a communication medium that connects one hub with all of the nodes in the network. Thus, a TDMA network wit a star configuration and two hubs is considered a two channel network. The process begins at block  300 .  
         [0033]     At block  302 , the process receives a clear to send (CTS) signal from a node in the network at a bus guardian of an asynchronous hub. The CTS signal indicates that the node that originated the CTS signal claims the next time slot on the channel associated with the hub. The process determines, at block  304 , if the guardian has received CTS signals from more than one node for the same time slot on the channel. If so, the process grants the node with the highest priority access to the channel at block  306  and proceeds to block  308 . If at block  304  there was no other CTS signal received at the hub, the process proceeds to block  308 .  
         [0034]     In one embodiment, the priority for a node is based on the port number of the port of the asynchronous hub that received the CTS signal. In one embodiment, a two channel system is used with independent hubs and bus guardians. One bus guardian gives priority to the node with the lowest port number and the other bus guardian gives priority to the node with the highest port number. Thus, when two nodes compete for the same time slot, one node will gain access to the time slot on one channel and the other node will gain access to the time slot on the other channel.  
         [0035]     At block  308 , the process relays the message from the node that was granted access to the channel.  
         [0036]     At block  310 , the process determines whether another CTS signal has been received from a different node for the same time slot on the channel. If another CTS signal has not been received, the process continues relaying the message at block  312  and returns to block  310 . If, however, the process does receive another CTS signal for the same time slot on the same channel, the process determines whether the node for the additional CTS signal has a higher priority than the node that has been granted access to the channel. If not, the process continues relaying the message at block  312 . If the process determines that the new CTS signal corresponds to a node with a higher priority, the process stops relaying the current message, inserts a period of silence to ensure that all receiving nodes can reliably detect the start of the next transmission and then relays the message from the higher priority node. The process returns to block  310 .  
         [0037]      FIG. 4  is a flow chart of one embodiment of a process for a node for determining a proper message among different messages received in the same time slot. The process begins at block  401 . At block  403 , the process receives two messages. At block  405 , the process determines whether the two messages are from the same source based on, for example, the source address in the messages. In another embodiment, the process uses port driven authentication as described in the &#39;323 and &#39;587 applications to determine the source of the messages. If so, the messages are processed at block  409  and the process returns to block  403 . If the two messages are not from the same source, the process determines which of the messages is from the correct source.  
         [0038]     At block  411 , the process determines the expected source of messages in the current time slot. For example, in one embodiment, the process uses a list of time slots and assigned nodes to determine the expected source and uses port driven authentication to select the proper message between the received messages. At block  413 , the process selects the message from the expected source and further processes the message. The process returns to block  403 .  
         [0039]     The methods and techniques described here may be implemented in digital electronic circuitry, or with a programmable processor (for example, a special-purpose processor or a general-purpose processor such as a computer) firmware, software, or in combinations of them. Apparatus embodying these techniques may include appropriate input and output devices, a programmable processor, and a storage medium tangibly embodying program instructions for execution by the programmable processor. A process embodying these techniques may be performed by a programmable processor executing a program of instructions stored on a machine readable medium to perform desired functions by operating on input data and generating appropriate output. The techniques may advantageously be implemented in one or more programs that are executable on a programmable system including at least one programmable processor coupled to receive data and instructions from, and to transmit data and instructions to, a data storage system, at least one input device, and at least one output device. Generally, a processor will receive instructions and data from a read-only memory and/or a random access memory. Storage devices or machine readable medium suitable for tangibly embodying computer program instructions and data include all forms of non-volatile memory, including by way of example semiconductor memory devices, such as EPROM, EEPROM, and flash memory devices; magnetic disks such as internal hard disks and removable disks; magneto-optical disks; and DVD disks. Any of the foregoing may be supplemented by, or incorporated in, specially-designed application-specific integrated circuits (ASICs).  
         [0040]     A number of embodiments of the invention defined by the following claims have been described. Nevertheless, it will be understood that various modifications to the described embodiments may be made without departing from the spirit and scope of the claimed invention. Accordingly, other embodiments are within the scope of the following claims.