Abstract:
A method including identifying data for transmission, determining a number of time-slots available for the transmission, and identifying a data packet from a plurality of data packets to transmit a portion of the data is disclosed.

Description:
FIELD OF THE INVENTION  
         [0001]    The present invention relates to data communications. Specifically, the present invention relates to a computing system and a method to dynamically select a data packet to efficiently transmit data.  
         BACKGROUND  
         [0002]    When transmitting data from one device to another, it is common for a large stream of data to be broken up into smaller packets of data in order to facilitate transmission. Breaking a large data stream into smaller packets facilitates retransmission and recovery should elements of the data stream become lost or corrupted. Breaking a large data stream into smaller packets may be completed using either hardware or software approaches.  
           [0003]    The current segmentation approaches tend to identify the possible packet types and then select a single packet that encompasses the entire data stream. This requires either utilizing a small packet or avoiding transmission if available time does not accommodate the packet.  
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0004]    The present invention is illustrated by way of example and not limitation in the figures of the accompanying drawings, in which:  
         [0005]    [0005]FIGS. 1A, 1B, and  1 C illustrate one embodiment of a flowchart of the method to dynamically select a data packet;  
         [0006]    [0006]FIG. 2 illustrates one embodiment of time-division multiplexing; and  
         [0007]    [0007]FIG. 3 illustrates one embodiment of a block diagram of the computing system to dynamically select a data packet.  
     
    
     DETAILED DESCRIPTION  
       [0008]    A computing system and a method to dynamically segment a data stream into smaller packets is disclosed. The packets are chosen from within the constraints of multiple packet choices with varying, but limited, packet sizes. Each segment of data is thus identified by a packet and transmission length.  
         [0009]    In this description, the term slot refers to a fixed amount of time for data transmission. This is typically a constant, such as 625 microseconds, by way of example. Also, in this description, the term packet refers to an identifier that specifies the characteristics of the transmission. A packet includes, but is not limited to, utilizing a fixed number of slots (e.g., 1, 3 or 5 slots) and having a maximum data length for transmission within the allowed slots. In short-range radio technologies, such as Bluetooth technology, the packet specifies the number of slots allowed, the maximum data that can be transmitted in the slots, and the data encoding style for Forward Error Correction, if any. In the ensuing description, the terms data packet type, and data packet are used interchangeably.  
         [0010]    The computing system and the method of the present invention allow data segmentation “on the fly.” In one embodiment, the algorithm of the present invention allows dynamic packet sizing to allow the packet to fit into the available timeslots. The present invention improves packet transmission, especially in protocols such as Bluetooth 1.0 specification. The present invention also reduces the need to put the segmentation methodology in software. By implementing the segmentation methodology in hardware, lower power and lower gate-count can be achieved, typically reducing manufacturing cost and providing longer battery life. The algorithm of the present invention can be implemented in products such as routers and switches.  
         [0011]    [0011]FIGS. 1A, 1B, and  1 C illustrate one embodiment of a flowchart of the method to dynamically select a data packet. At block  102 , the desired data transfer length is determined. In other words, the length of the data to be segmented and transmitted is identified. At block  106 , the available packets are identified. A data packet is defined by the number of time-slots required to transmit the packet, the maximum data length that can be transmitted by the packet, and possible minimum data length requirement of the packet.  
         [0012]    At block  110 , the maximum available time-slots to transmit the data are determined. In one embodiment, multiple agents are contending for transmitting data to multiple devices through a transmission medium. In this embodiment, an arbitration mechanism such as time-division multiplexing is implemented to iterate over all the possible segmentation possibilities and select an agent and a corresponding device. For example, an algorithm can be implemented to perform time-division multiplexing of isochronous traffic with available slots for asynchronous traffic as illustrated in FIG. 2. In another embodiment, a single agent transmits data to a single device through the transmission medium. In this case, block  110  is deleted from the flowchart because the number of slots available for the data transfer are infinite.  
         [0013]    At block  114 , from the available data packets identified at block  106 , the data packets that fit into the available time-slots of block  110  are identified. If there are multiple format options for segmenting the data into multiple packets, these data packets are identified at block  114 . At block  118 , from the data packets identified at block  114 , the packets that meet a minimum transfer length requirement are identified. In other words, packets that are too small for the transfer length are not identified in block  118 . Blocks  114  and  118  thus eliminate the packets that are too large for the available time-slots and the packets that are too small for the data transfer length.  
         [0014]    At block  122 , from the packets identified at block  118 , the packets that can successfully transfer the entire length are identified. The packets identified at block  122  fit into the available time-slots, meet the minimum packet criteria, and can successfully transmit the entire data length.  
         [0015]    At block  136 , a determination is made whether any data packets were identified at block  122 . At block  138 , the packets identified at block  122  are submitted to block  146 . If no data packets are identified at block  122 , at block  140 , the packets identified at block  118  are submitted to block  146 . The packets identified at block  118  meet the slot and the minimum length criteria.  
         [0016]    Block  146  is also referred to as the priority selection block. At block  146 , from the packets identified at blocks  122  or  118 , the packet that can send the most data in the shortest amount of time is identified. At block  146 , if no packets are received from the blocks  122  or  118 , it is determined that data segmentation on this data stream cannot occur for the parameters.  
         [0017]    At block  150 , data is transmitted through the packet identified at block  146 . At block  150 , a determination is made whether the entire desired data transfer length was transmitted. If yes, the flow diagram ends at block  158 . If no, the new desired data transfer length is at block  164  by subtracting the data length transmitted at block  150  from the desired data transfer length of block  102 . Following, at block  168 , the flow diagram returns to block  168  to process the new desired data transfer length calculated at block  102 .  
         [0018]    The method illustrated in FIG. 1 is now illustrated by way of an example. The example is related to the Bluetooth wireless technology which supports both circuit switching for isochronous traffic as well as packet switching for asynchronous traffic. In this example, the desired data transfer length is 1000 bytes of asynchronous data. The available data packets are illustrated in Table 1.  
                                 TABLE 1                           Bluetooth supported Data Packets for Asynchronous Traffic                Data Packets   Time-Slot   Payload length (bytes)                       DM1   1   0-17           DH1   1   0-27           DM3   3   0-121           DH3   3   0-183           DM5   5   0-224           DH5   5   0-339           AUX1   1   0-29                      
 
         [0019]    DM1 and DH1 packets are preferred in a noisy environment because they require only one time-slot for transmission and contain a small amount of data. The transmission of the DM1 and DH1 packets is more robust and less prone to error than the DM3 and DH3 packets. The advantage of the DM3 and DH3 packets is that they can transmit a larger amount of data than the DM1 and DH1 packets. Thus, the DM3 and DH3 packets allow the transmitter logic to be put in a low power mode earlier than the DM1 and DH1 packets.  
         [0020]    [0020]FIG. 2 illustrates the maximum available time-slots to transmit the 1000 bytes of asynchronous data. According to FIG. 2, every fourth time-slot  204  is reserved to service the isochronous traffic. The asynchronous traffic can take place in the three time-slots  208  between the two time-slots  204  reserved for isochronous traffic.  
         [0021]    According to Table 1, the packets DM1, DH1, DM3 and DH3 fit into the three available time-slots. DM1 and DH1 are too small and thus do not meet the minimum transfer length requirement. None of the packets of Table 1 can transmit the entire 1000 bytes. DH3 is preferable to DM3 because it can transmit more data. Following the transmittal of 183 bytes through DH3, the new desired data transfer length is 817 bytes. The algorithm of this example is repeated for the 817 bytes of asynchronous data.  
         [0022]    Since Bluetooth wireless technology is able to support a network of up to 8 devices, this example can be extended to consider the scheduling of several packets of asynchronous traffic targeting different devices. The data type determination based on available slots and packet length becomes proportionally complicated.  
         [0023]    [0023]FIG. 3 illustrates a block diagram of an exemplary embodiment of the computing system  300  to dynamically select a data packet. The computing system can be a component of a network server or a network client. The block diagram is a high level conceptual representation and may be implemented in a variety of ways and by various architectures.  
         [0024]    In one embodiment, the data packet select module  340  is configured to perform the algorithm illustrated in the flowchart of FIG. 1. In one embodiment, the packet select module  340  is a programmable module implemented in hardware. In another embodiment, the packet select module  340  is a programmable module implemented in firmware.  
         [0025]    In another embodiment, the Random Access Memory (RAM)  308  includes the instructions to execute the algorithm illustrated in FIG. 1. In yet another embodiment, the Read Only Memory (ROM)  306  includes the instructions to execute the algorithm illustrated in FIG. 1. The instructions stored in the RAM  308  or the ROM  306  are executed by the Central Processing Unit (CPU)  304 .  
         [0026]    The computer system  300  also includes communications means such as the bus system  302  for communicating information. The RAM or other dynamic storage device  308  is coupled to the bus  302  for storing information and instructions to be executed by the CPU  304 . The ROM and/or other static storage device  306  is coupled to the bus  302  for storing static information and instructions for the CPU  304 . The computing system  300  can also include storage means such as the data storage device  310  coupled to the bus  302 . The computing system  300  can also be coupled via the bus  302  to the display device  320 , audio  322 , keyboard  324 , pointer  326 , miscellaneous input/output (I/O) device  328 , and communications device  330 . The I/O device  328  can be connected via the input/output port  329  to other devices or systems.  
         [0027]    These and other embodiments of the present invention may be realized in accordance with these teachings and it should be evident that various modifications and changes may be made in these teachings without departing from the broader spirit and scope of the invention. The specification and drawings are, accordingly, to be regarded in an illustrative rather than restrictive sense and the invention measured only in terms of the claims.  
         [0028]    In addition, the instructions to perform the methods as described above could alternatively be stored on other forms of computer-readable mediums. A machine-readable medium includes any mechanism that provides (e.g., stores and/or transmits) information in a form readable by a machine (e.g., a computer). A machine-readable medium is understood to include any mechanism for storing or transmitting information in a form readable by a machine (e.g., a computer). For example, a machine-readable medium includes read only memory (ROM); random access memory (RAM); magnetic disk storage media; optical storage media; flash memory devices; electrical, optical, acoustical or other form of propagated signals (e.g., carrier waves, infrared signals, digital signals, etc.).