Broadcasting of packets in an RF system.

Background of the Invention

0001This invention is directed to a radio frequency (RF) packet communication system in which selected packets are broadcast by a control module to a plurality of user modules. <u>Broadcasting</u> refers to a transmission of information intended to be received by a plurality of remote devices with different addresses. This invention is especially suited for an RF system in which directional antennae are utilized.

0002One simple broadcast algorithm is known as flooding, in which each incoming packet is sent out on every outbound line except the one it arrived on. Obviously this technique generates a large number of duplicate packets. Typically some method is used to damp or reduce the number of duplicates.

0003In an Ethernet local area network (LAN), a predetermined destination address in the header of a packet identifies the packet as one to be broadcast. The level of broadcast can either be to all members of the network or to a defined group. Receiving units interpret the packet as addressed to them if a general broadcast is detected or if a group broadcast adress is detected in which they are a member. Units which are not part of the selected group reject the packet as not addressed to them.

0004Using a broadcast technique in an RF LAN environment presents difficulties. The error characteristic of the RF system, especially where the communication path is not line of sight, will probably be poorer than the error characteristic of a wired or cabled LAN. A further difficulty is presented if the RF system uses directional or sectorized antennas where only one antenna is active at a time. The best antenna utilized by a first RF unit when communicating with a second unit will typically be different than the best antenna for communicating with a third unit. Multiple antenna choices complicate the use of broadcasting in an RF LAN since a signal sent over a selected antenna by the transmitting unit may not be received by all other units.

Brief Description of the Drawings

0005FIG. 1 illustrates is a block diagram of an RF LAN system in accordance with the present invention.

0006FIG. 2 is a block diagram illustrating a control module and a user module as shown in FIG. 1.

0007FIG. 3 illustrates the format for an Ethernet packet.

0008FIG. 4 illustrates a format for an RF packet in accordance with the present invention.

0009FIG. 5 is a flow diagram illustrating the transmission of a packet by a user module in accordance with the present invention.

0010FIG. 6 is a flow diagram illustrating the processing of a packet by a control module in accordance with the present invention.

0011FIG. 7 is a flow diagram illustrating the processing of a received packet by a user module in accordance with the present invention.

0012FIG. 8 is a flow diagram illustrating a fragment routine utilized to break larger packets into smaller packets for transmission in accordance with the present invention.

0013FIG. 9 is a flow diagram illustrating an exemplary timeout timer utilized in accordance with FIG. 7.

Description of a Preferred Embodiment

0014Before describing an embodiment of the present invention, it is believed that an overview of the invention will aid the reader in understanding the invention. The problems identified in utilizing a broadcast technique in an RF plan system are minimized, if not overcome, by the present invention. In order to maximize the probability that each user module will receive a packet, the control module preferably transmits each packet sequentially over each of its sectorized antennas and retransmits the same packet a number of times over each antenna to further enhance the probability of reception by each user module. As part of the RF LAN system protocol, each user module marks a packet as being a broadcast type packet so that the control module will recognize it as a packet to be broadcast. This allows the control module to easily determine if packets received from user modules are to be broadcast. Packets from the user modules which are not marked are handled using a normal destination transmission protocjol where only the best antenna for communicating with the destination user module is used. Thus, the present invention contemplates an RF LAN system in which broadcasting is permitted where appropriate to maximize throughput while using a normal transmission protocol for other packets.

0015FIG. 1 illustrates an RF LAN system in accordance with the present invention. A plurality of user modules (UM) 20 are capable of RF communications with control module (CM) 22. Each user module 20 is connected to one or more user devices such as a personal computer (PC) 24 by wire connections 26. The CM is connected to packet network 28 by wire or optical link 30. The packet network 28 in the illustrative embodiment may utilize an Ethernet protocol and may also include other RF LANs.

0016FIG. 2 shows an exemplary embodiment of a CM in accord with the present invention. A communications unit 30 includes an RF transmitter, RF receiver, and a microprocessor system which controls the operation of the unit. An antenna system 32 includes six directional antennae A1-A6. Each antenna provides approximately 60° of coverage in the horizontal plane so that the entire antenna system is capable of 360° coverage. One antenna is selected by unit 30 for use at a given time.

0017The communications unit 30 and antenna system 32 are also suited for use as user modules. When a UM is in communication with the CM, the UM will normally select the antenna with the best signal quality for use while the CM simultaneously selects its antenna with the best signal quality for use in communicating with the UM. It will be apparent to those skilled in the art that for optimal communications the CM will likely select different antennae for communicating with different UMs. This is especially true where the RF LAN system is situated in a building with the CM located centrally in an area and the UMs located about it. In the illustrative embodiment, a single frequency is utilized for RF communications between the CM and UMs. Thus each Um is capable of receiving a communication transmitted from the CM.

0018FIG. 3 illustrates a typical packet format 34 used for the transmission of information. The format includes a destination address 36, a source address 38, a type designator 40, information 42 to be communicated, and a cyclic redundancy check (CRC) 44 used for error checking. Portions 36, 38, and 40 comprise what is commonly referred to as a header. In the preferred embodiment the data format 34 follows an Ethernet format in which the destination address contains a predetermined address that identifies the packet as a general broadcast packet to all devices, as a limited broadcast packet to a subgroup of devices, or as a non-broadcast packet destined for a single address.

0019FIG. 4 illustrates an exemplary data format 46 utilized to define packets to be transmitted by RF communications between the user modules and the control module. These RF packets are used to carry information between modules including Ethernet packets. The format includes a general information carrying field 52, a CRC 54, and a header portion 48 which includes a broadcast field 50 and a fragment identification field 51. Field 50 is utilized in the present invention as a flag which determines whether or not the packet 46 is to be handled as a broadcast packet or as a single destination type packet. Field 51 is used to identify packets 46 in which the formation fields 52 of several packets (packet fragments) are to be combined in order to recreate original data too long to fit into one packet field 52. Field 51 contains the total number of packet fragments sent and the specific number of each packet fragment, i.e. fragment No. 2 of 4 total fragments. It will be apparent to those skilled in the art that header 48 includes additional overhead information needed by packet systems including destination address, source address, and other miscellaneous overhead information and instructions.

0020Information field 52 may contain an entire Ethernet packet 34 if it is not longer than a predetermined number L of bytes. A maximum length of packet 46 is determined in accordance with the error probabilities associated with the RF LAN. The length is selected in view of the error probabilities and the percent of overhead information transmitted with each packet.

0021FIG. 5 is flow diagram which explains the processing of packets 46 originated by a user module and transmitted to the control module. These steps start at BEGIN entry 56. At step 58, a UM receives a packet 34 from a PC 24 connected to the UM. In step 60, processing is transferred to the fragment routine described in connection with FIG. 8. The purpose of the fragment routine is to determine if packet 34 is so large that it has to be separated into fragments and, if so, to generate new RF packets 46 for each such fragment.

0022Following a return from the fragment routine 60, decision step 62 determines if the packet 34 is of the broadcast type. This determination may be made by inspecting the destination address 36 in packet 34 to determine if it corresponds to a predetermined general or limited broadcast type. If the determination of step 62 is YES, the M (multicast) flag in field 50 of each UM packet 46 is set. This flag is not set if the decision by step 62 is NO. In step 66 the UM transmits N of packets 46 to the CM. The number N represents the number of fragments determined by the fragment routine. This routine terminates at EXIT 68.

0023FIG. 6 is a flow diagram illustrating how the control module processes packets received from a user module 20 or the packet network 28. The process starts at step 70 in which the variable "Net" is set equal to zero. A determination is made in step 71 if the received packet came from the packet network, i.e. via channel 30. If YES, step 72 causes a jump to the fragment routine and upon return sets variable Net equal to one. Step 73 is executed either upon a NO decision by step 71 or upon completion of step 72. It should be noted that before processing by step 73 begins the received packet will be in a packet format 46. If the packet received by the CM came from a UM, it will be received in the packet 46 format directly. If the CM received the packet from the packet network in format 34, fragment routine called for in step 72 will have created appropriate packets 46 to carry the information originally contained in the packet format 34.

0024In step 73, a determination is made if the received packet is of the broadcast type. If NO, step 74 causes the CM to transmit the N packets 46 to the UM to which it is addressed. This routine then ends at EXIT 75. A YES determintation by step 73 indicates that the received packet is to be broadcast. In step 76 a determination is made if Net equals zero. This determines if the received packet being processed was sent by a UM. If YES, determination step 77 determines if all fragments have been received. Upon a NO decision by step 77, step 78 stores the received fragment and the routine terminates at EXIT 79. A YES determination by step 77 results in step 80 assembling the fragments into the original packet 34 which is sent to the network 28.

0025Upon a NO decision by step 76 or upon completion of step 80, step 81 sets the M flag in each packet. This will provide information to the UMs receiving the broadcast that the packet is of the broadcast type and should be received by each UM.

0026Step 82 consists of a series of three nested DO loops which causes the packets 46 to be broacast. Variable K corresponds to a specific one of different directional antennae at the CM, with A corresponding to the total number of available antennae. Thus, the first nested loop causes the packet fragment N to be transmitted on each of antenna. The variable J in the second nested loop determines how many times (repeats) R the game packet fragment is to be retransmitted over each of the antennas. The third nested loop includes a variable H in which the number N represents the number of packet fragments and hence the number of packets 46 that have to be transmitted. Thus, in step 82 each of the packet fragments is transmitted over each antenna R times. In this example, A≃6, 1≦R≦5. Following the transmission of packets this routine ends at EXIT 88.

0027FIG. 7 is a flow diagram illustrating the processing of packets received by a user module from the control module. Following the beginning of this routine at step 84, decision step 85 determines if the received packet's header has M = 1, i.e. if the broadcast flag is set. Upon a NO decision, decision step 86 determines if the destination address of the packet matches the UM address. This system also contemplates that each device or PC coupled to a user module may have a separate address. In this case the destination address of the received packet would have to be compared to each of the associated user device addresses. A NO decision by step 86 results in termination of this routine at EXIT 87 since the received packet need not be processed further by the user module. A YES decision by step 86 causes the address specific packet to be accepted, decoded, and delivered by step 88 to the addressed user device. Following this step the routine exits terminates at EXIT 89.

0028Following a YES determination by step 85, the received packet is accepted and decoded by step 90 since the packet is a broadcast type to be received by each UM. Decision step 92 determines if the received broadcast packet is a duplicate of a previously recieved packet. If YES, the routine terminates at EXIT 89 since the UM need not reprocess and another duplicate of a previously received packet containing the same information. It will be remembered that duplicate packets are possible since each packet or packet fragment will be rebroadcast on different antennas and repeated transmissions made. If the packet is not a duplicate, that is a NO decision by step 92, decision step 93 determines if the received packet constitutes one of several packet fragments which contain the original information. This determination is made from information contained in field 51 of the packet 46 which contains the total number of packet fragments containing the original information and the particular number of the packet fragment. A NO determination by step 93 results in step 94 delivering the single packet to the user device(s) coupled to the user module. This routine then terminates at EXIT 95.

0029A YES determination by step 93 corresponds to a determination that the original information being transmitted was segregated into multiple packet fragments. In step 96 the received fragment is stored and a timeout timer is set to time T on receiving the first fragment, i.e. if N = 1. The action of the timeout timer is described with regard to FIG. 9. In determination step 97, a NO decision terminates the routine at EXIT 95. This routine terminates since additional packet fragments must be received before the original information can be fully recovered. A YES determination by step 97 results in step 98 assembling all of the required packet fragments into the original packet and delivering it to the corresponding user device(s) coupled to the user module. This routine then terminates at EXIT 99.

0030It will be noted that in step 96 the timeout timer is reset when the first packet fragment is received. The timeout timer functions to provide a time window in which all remaining packet fragments must be received. If the timeout timer reaches time T whithout being reset, which occurs upon receipt of the last fragment in the series, the system assumes that at least one packet fragment is missing and aborts the attempt to recover the original information being broadcast in multiple packet fragments.

0031FIG. 8 is a flow diagram of the packet fragment routine. This routine begins at entry point 100. Determination step 102 determines if the received packet is greater than L (length) bytes. A NO decision results in step 104 setting N = 1. This corresponds to an original packet 34 that can be contained within one packet 46. A YES decision by step 102 results in the original packet 34 being separated into N fragments of L bytes. It will be apparent to those skilled in the art that the last fragment N may contain less than L bytes. In step 108 a DO loop generates a new packet 46 for each of the N fragments. Each of the packet fragments is identified as being a particular number in a total number of N fragments in field 51. This enables the receiving module to determine that all packet fragments required have been received. The routine terminates at RETURN 110.

0032FIG. 9 is a flow diagram of a timeout timer routine as referenced in step 92. This routine begins at entry 112. In step 114 a determination is made as to whether the timer is set. A NO determination results in this routine terminating at EXIT 116. A YES determination by step 114 results in step 118 determining if time T has expired. A NO determination terminates routine at EXIT 116. A YES determination results in step 120 deleting any previously stored packet fragments and resetting the timeout timer. This action occurs since all packet fragments in the current fragment series has not been received within a predetermined time. If not received within this time the system determines that it is not likely that the complete series will be received and thus aborts further attempts to reconstruct the original packet. The routine terminates at EXIT 122. It is believed to be apparent to those skilled in the art that the timeout timer routine will be executed by the system frequently enough to ensure that the predetermined time T can be reasonably monitored.

0033The present invention provides an RF LAN system in which packet communications is enhanced by permitting selected packets to be broadcast to all user modules while maintaining destination address routing of other packets. The probability of reception of a broadcast packet is improved by transmission from multiple directional antennae and rebroadcasts of the packet. The system also generates packet fragments to accommodate the more efficient transmission of large input packets.

0034Although an embodiment of the present invention has been described and illustrated in the drawings, the scope of the invention is defined by the claims which follow.