Abstract:
A device and method for scheduling packet transmission are disclosed. The disclosed device includes: an interface unit configured to transmit and receive a packet; a controller configured to calculate a local time and an ARQ time from a packet to be transmitted, where the local time is determined in proportion to a packet delay bound, and the ARQ time is determined based on the local time and the packet delay bound; a queue in which the packet to be transmitted is inputted; and a scheduler configured to determine a transmission order of packets inputted in the queue based on at least one of the local time and the ARQ time. The disclosed device provides the advantage of efficient packet transmission in a multi-hop wireless network.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application claims the benefit of Korean Patent Application No. 10-2013-0049084, filed with the Korean Intellectual Property Office on May 1, 2013, the disclosure of which is incorporated herein by reference in its entirety. 
       TECHNICAL FIELD 
       [0002]    The present invention relates to a device and method for scheduling packet transmission. 
       RELATED ART 
       [0003]    As the amount of multimedia traffic increases for real-time services involving digital audio and digital video applications, various techniques are being developed to guarantee the QoS of each packet. A scheduling algorithm can be regarded as a representative example of a technique for ensuring packet QoS, and various scheduling algorithms are being developed in the field of wired networks. Existing scheduling algorithms in wired networks include EDF (Earliest Deadline First), CEDF (Coordinated EDF), G-EDF (Global-EDF), etc. EDF scheduling is an algorithm for determining transmission order by assigning higher priority to packets that have smaller delay bounds, and CEDF scheduling and G-EDF scheduling are algorithms for determining transmission order by assigning higher priority to packets having smaller delay bounds while incorporating coordination between nodes along the packet transmission path and were designed to guarantee QoS in packets having multi-hop paths. However, the algorithms described above were designed in consideration of wired networks and may not be efficient when applied directly to wireless networks. 
         [0004]    A wireless network has unique properties compared to the wired network and requires a scheduler design that considers these properties. Some of the properties of the wireless network are as follows. In a wireless network, the channel capacity may vary according to the position of the user and according to time. Also, changes in channel status may cause errors during packet transmission, and when an error occurs for a packet, a retransmission of the packet is needed. As an existing scheduling algorithm for a wireless network, an algorithm has been proposed for supporting constant bitrate (CBR) traffic for a single-hop wireless network that uses a Markov decision process (MDP). Expanding on this method, Channel-Aware EDD (CA-EDD) was proposed as a scheduling algorithm that considers both delay bounds and channel status and uses dynamic programming (DP). However, these algorithms were designed for a downlink wireless network and do not consider packet transmission having multi-hop paths. 
       SUMMARY 
       [0005]    An aspect of the invention proposes a device and method for scheduling packet transmission that can transmit packets efficiently in a multi-hop network. 
         [0006]    One aspect of the invention provides a device for scheduling packet transmission that includes: an interface unit configured to transmit and receive a packet; a controller configured to calculate a local time and an ARQ time from a packet to be transmitted, where the local time is determined in proportion to a packet delay bound, and the ARQ time is determined based on the local time and the packet delay bound; a queue in which the packet to be transmitted is inputted; and a scheduler configured to determine a transmission order of packets inputted in the queue based on at least one of the local time and the ARQ time. 
         [0007]    The queue may include a retransmission packet queue, in which a packet that is to be retransmitted is inputted, and an initial transmission packet queue, in which a packet that is to be transmitted initially is inputted. 
         [0008]    The controller may use the local time first and then use the ARQ time when calculating the local time and the ARQ time. 
         [0009]    When the ARQ time for a particular packet becomes 0 or lower, then the packet may be dropped. 
         [0010]    In a multi-hop network, the local time may be set for each node, and the ARQ time may be set to a fixed value regardless of node. 
         [0011]    If not all of the local time is used for a packet at a particular node transmitting the packet in the multi-hop network, the remaining local time may be added to the ARQ time to modify the ARQ time. 
         [0012]    The controller may determine whether or not the packet to be transmitted is a retransmitted packet and may input the packet to the retransmission packet queue if the packet is a retransmitted packet and input the packet to the initial transmission packet queue if the packet is not a retransmitted packet. 
         [0013]    The scheduler may assign a higher priority level to packets standing by in the retransmission packet queue than to packets standing by in the initial transmission packet queue. 
         [0014]    The scheduler may determine priority levels for packets standing by in the initial transmission packet queue by using the local times. 
         [0015]    The scheduler may determine priority levels for packets standing by in the retransmission packet queue by using the ARQ times. 
         [0016]    If a particular packet from among the packets standing by in the initial transmission packet queue uses up all of its local time, then the controller may input the packet in the retransmission packet queue. 
         [0017]    When a packet is received from a new flow, the controller may determine whether or not to accept the packet from the new flow. 
         [0018]    The controller may determine whether or not to receive the packet from the new flow by considering the probability of a delay bound being violated and the processing capacity that would be required if the new packet is received. 
         [0019]    Another aspect of the invention provides a method for scheduling packet transmission that includes: (a) inputting a packet to be transferred in a queue; (b) calculating a local time and an ARQ time from the packet to be transmitted, the local time determined in proportion to a packet delay bound, the ARQ time determined based on the local time and the packet delay bound; and (c) determining a priority level of the packet to be transmitted based on at least one of the local time and the ARQ time. 
         [0020]    A method and device for scheduling packet transmission according to certain embodiments of the invention provide the advantage of efficient packet transmission in a multi-hop wireless network. 
         [0021]    Additional aspects and advantages of the present invention will be set forth in part in the description which follows, and in part will be obvious from the description, or may be learned by practice of the invention. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0022]      FIG. 1  illustrates an example of a communication system to which a method for scheduling packet transmission based on an embodiment of the invention may be applied. 
           [0023]      FIG. 2  illustrates a header structure for a transmitted packet according to an embodiment of the invention. 
           [0024]      FIG. 3  illustrates changes in local time and ARQ time when a packet is transmitted according to an embodiment of the invention. 
           [0025]      FIG. 4  is a block diagram of a device for scheduling packet transmission according to an embodiment of the invention. 
           [0026]      FIG. 5  illustrates the structure of a multi-queue  404  according to an embodiment of the invention. 
           [0027]      FIG. 6  is a flowchart illustrating the flow of a method for scheduling packet transmission according to an embodiment of the invention. 
       
    
    
     DETAILED DESCRIPTION 
       [0028]    As the present invention allows for various changes and numerous embodiments, particular embodiments will be illustrated in the drawings and described in detail in the written description. However, this is not intended to limit the present invention to particular modes of practice, and it is to be appreciated that all changes, equivalents, and substitutes that do not depart from the spirit and technical scope of the present invention are encompassed in the present invention. In describing the drawings, like reference numerals are used for like elements. 
         [0029]      FIG. 1  illustrates an example of a communication system to which a method for scheduling packet transmission based on an embodiment of the invention may be applied. 
         [0030]    Referring to  FIG. 1 , a communication system to which a packet transmission scheduling method according to an embodiment of the invention is applied can include multiple nodes and may be a multi-hop network communication system in which packets are transmitted over multiple relay nodes A, B, C from a source node S to a destination node D. 
         [0031]    A packet may be transmitted from the source node S, and the relay nodes A, B, C may relay the packet such that the packet transmitted from the source node S reaches the destination node D. 
         [0032]    In a conventional method of scheduling packet transmission, a variable called “delay bound” may be used to determine whether or not to drop a packet. For example, a scheduling for packet transmission may entail assigning a delay bound for each hop, and dropping the packet if the delay bound is exceeded at a particular hop. 
         [0033]    Also, if a transmission error occurs during a packet transmission, a retransmission from the source node S of the packet for which the error occurred may be requested, and the source node S may again transmit the packet of which retransmission was requested. The retransmission can take place over several rounds, and if the time lapsed for the initial transmission and the retransmission exceeds the delay bound, the packet may be dropped. 
         [0034]    Also, in a conventional packet transmission scheduling method, priority levels may be set for packets standing by in a queue based on the delay bounds assigned to each packet, where a packet having a smaller delay bound may be given higher priority over a packet having a larger delay bound. 
         [0035]    A device for scheduling packet transmission according to an embodiment of the invention may be equipped for each node, to assign priority levels to the packets provided to each node for transmitting the packets. 
         [0036]    A packet transmit scheduling based on an embodiment of the invention may schedule packet transmission by using two variables, the local time and the ARQ (Automatic Repeat Request) time. 
         [0037]    The local time refers to the time allotted at a transmitting node for each hop in a multi-hop network, and may serve as a basis for setting priority levels for the packets. That is, when multiple packets are standing by in a queue at a transmitting node, the priority levels for packet transmission may be determined based on the local times of the respective packets. 
         [0038]    The ARQ time may serve as a basis for determining whether or not a packet is to be dropped and may also be used in setting the priority levels of the packets when necessary. When the ARQ time of a particular packet reaches 0, the packet may be dropped. 
         [0039]    Using i to represent a flow, n to represent a node, D, to represent the delay bound at flow i, and N i  to represent the total number of nodes, the local time d i,n  at each node can be defined by Equation 1 shown below. 
         [0000]        d   i,n =(1−α) D   i /( N   i −1)   [Equation 1]
 
         [0040]    As can be seen from Equation 1 above, the local time is a variable that is proportional to the delay bound. The weight variable a for used in determining the local time may be determined according to the level of importance of the packet. 
         [0041]    The ARQ time may be determined by the delay bound and the established local time. The following Equation 2 expresses the ARQ time allotted to the q-th packet at node n for flow i. 
         [0000]    
       
         
           
             
               
                 
                   
                     a 
                     
                       i 
                       , 
                       n 
                     
                     q 
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             
                               
                                 D 
                                 i 
                               
                               - 
                               
                                 
                                   ∑ 
                                   
                                     j 
                                     = 
                                     1 
                                   
                                   
                                     
                                       N 
                                       i 
                                     
                                     - 
                                     1 
                                   
                                 
                                  
                                 
                                   d 
                                   
                                     i 
                                     , 
                                     j 
                                   
                                 
                               
                             
                             , 
                           
                         
                         
                           
                             n 
                             = 
                             1 
                           
                         
                       
                       
                         
                           
                             
                               
                                 d 
                                 
                                   i 
                                   , 
                                   
                                     n 
                                     - 
                                     1 
                                   
                                 
                               
                               + 
                               
                                 a 
                                 
                                   i 
                                   , 
                                   
                                     n 
                                     - 
                                     1 
                                   
                                 
                                 q 
                               
                               - 
                               
                                 s 
                                 
                                   i 
                                   , 
                                   
                                     n 
                                     - 
                                     1 
                                   
                                 
                               
                               - 
                               
                                 τ 
                                 
                                   i 
                                   , 
                                   
                                     n 
                                     - 
                                     1 
                                   
                                 
                                 q 
                               
                             
                             , 
                           
                         
                         
                           
                             n 
                             &gt; 
                             1 
                           
                         
                       
                     
                   
                 
               
               
                 
                   [ 
                   
                     Equation 
                      
                     
                         
                     
                      
                     2 
                   
                   ] 
                 
               
             
           
         
       
     
         [0042]    In Equation 2 above, s i,n  represents service time, and τ q   i,n  represents a sum of the queuing delay time and transmission delay time for the q-th packet. 
         [0043]    When transmitting a packet, the local time may be expended first, and the ARQ time may be expended when all of the local time has been expended. Since the local time is expended first and the ARQ time is expended afterwards, having the ARQ time reach 0 is the same as reaching the delay bound, and hence the packet may be dropped. 
         [0044]    If not all of the local time was expended in a first hop, in which a packet was transmitted from a first node to a second node, then the remaining local time may be added to the ARQ time in the second hop. For example, if the local time were 1 second at the first hop and 0.5 seconds were used in the first hop so that 0.5 seconds of the local time is left remaining, then the remaining local time may be added to the ARQ time. 
         [0045]      FIG. 2  illustrates a header structure for a transmitted packet according to an embodiment of the invention. 
         [0046]    Referring to  FIG. 2 , a packet for which a packet scheduling method according to an embodiment of the invention is used can include a transmission number field  200 , a local time field  202 , and an ARQ time field  204  as header information. 
         [0047]    In the transmission number field  200 , the information for checking whether the packet is a retransmitted packet may be recorded. For instance, flag information can be recorded for checking for retransmission, or information on the specific number of transmissions can be recorded. 
         [0048]    For example, flag information can be recorded in the transmission number field  200 , with “0” representing an initial transmission and “1” representing a retransmitted packet. 
         [0049]    In the local time field  202 , information regarding the local time initially set at the transmitting node may be recorded. The local time recorded in the local time field  202  may be used as information for setting the priority levels of packets in a queue. 
         [0050]    In the ARQ time field  204 , information on the remaining ARQ time may be recorded. As described above, when all of the ARQ time is expended, the corresponding packet may be dropped. 
         [0051]      FIG. 3  illustrates changes in local time and ARQ time when a packet is transmitted according to an embodiment of the invention. 
         [0052]    Referring to  FIG. 3 , a communication system is illustrated that is composed of a source node S, two relay nodes A, B, and a destination node D, where a packet is transmitted from the source node S to the destination node D in the order of S-A-B-D. That is, the packet is transmitted from the source node S to the destination node D over through hops. 
         [0053]    Suppose that the total delay bound is 1 second, and that the local time assigned to the transmitting node for each hop is 0.1 second. As there are three hops, the total sum of the local times assigned to the transmitting nodes of the respective hops is 0.3 seconds, and therefore the ARQ time is 0.7 seconds. 
         [0054]    Suppose 0.05 seconds are expended in the first hop until the transmitting node transmitted the packet. Then, in the first hop, not all of the local time is used, and 0.05 seconds of the local time remains. 
         [0055]    The source node S of the first hop may add the remaining local time, 0.05 seconds, to the ARQ time, and the packet reflecting the modified ARQ time information may be transmitted to the first relay node A. Since 0.05 seconds of additional ARQ time was provided, the local time is 0.1 second and the ARQ time is 0.75 seconds at the first relay node A. 
         [0056]    If 0.2 seconds are expended at the first relay node A in transmitting the packet (including the transmission delay in the first hop), then 0.1 second of the local time is expended, and 0.1 second of the ARQ time is then used. Here, the ARQ time is changed from 0.75 seconds to 0.65 seconds. 
         [0057]    The first relay node A may incorporate the changed ARQ time in the header information and transmit the packet to the second relay node. 
         [0058]    If 0.3 seconds are expended at the second relay node B in transmitting the packet to the destination node D (including the transmission delay in the second hop), then 0.1 second of the local time is expended, and 0.2 seconds of the ARQ time are then used. Thus, the ARQ time is changed from 0.65 seconds to 0.45 seconds. 
         [0059]    The second relay node B may incorporate the changed ARQ time in the header information and transmit the packet to the second relay node. 
         [0060]    As seen in  FIG. 3 , each transmitting node, when transmitting a packet, may first use the local time and may use the ARQ time when the local time is used up. When all of the ARQ time is expended, the corresponding packet may be dropped. 
         [0061]      FIG. 4  is a block diagram of a device for scheduling packet transmission according to an embodiment of the invention. 
         [0062]    The packet transmission scheduling device illustrated in  FIG. 4  may be equipped at each node of a multi-hop network. 
         [0063]    Referring to  FIG. 4 , a packet transmission scheduling device according to an embodiment of the invention may include an input/output interface unit  400 , a processor unit  402 , a multi-queue  404 , and a scheduler  406 . 
         [0064]    The processor unit  402  may include a controller  410  and a memory device  412 , and the controller  410  may include a local time computation unit  420 , an ARQ time computation unit  422 , and a CAC (Call Admission Control) controller  424 . 
         [0065]    The input/output interface unit  400  may include an input interface and an output interface. The data received from other nodes may be inputted via the input interface. The data to be transmitted from the node may be outputted via the output interface. 
         [0066]    The controller  410  may serve to determine whether or not a packet received via the input interface is to be inputted to the multi-queue  404  and to manage the ARQ time and local time of a packet. 
         [0067]    The local time computation unit  420  of the controller may analyze the header information of a packet received via the input interface to check the local time of the packet and may measure the amount of local time expended. The local time computation unit  420  of a source node, where the packet is generated, may compute the local time of the generated packet. The local time can be computed as in Equation 1. 
         [0068]    The ARQ time computation unit  422  may check the ARQ time recorded in the packet received from the input interface. Also, the ARQ time computation unit  422  may measure the amount of ARQ time expended. The ARQ time computation unit  422  may lastly check the duration of time for which the packet remained at the node and may update the ARQ time when the packet is outputted via the output interface. 
         [0069]    When a packet of a new flow is received, the CAC controller  424  may determine whether or not to process the packet of the flow. Here, a flow can be defined as a source from which a packet is generated. For example, a first flow can be a flow for streaming packets transmitted from a particular video server, while a second flow can be a flow for game data packets transmitted from a game server. 
         [0070]    The CAC controller  424  may determine whether or not to process the new packet in consideration of the probability of violating a delay bound if the packet of the new flow were to be processed and the processing capacity of the node for guaranteeing QoS. The CAC controller  424  may accept and process a packet of a new flow if the probability of violating a delay bound is lower than or equal to a preset threshold and if the processing capacity for guaranteeing QoS is smaller than or equal to the maximum processing capacity of the node. 
         [0071]    According to an embodiment of the invention, the probability of violating the delay bound for a flow i can be computed as in Equation 3 shown below. 
         [0000]    
       
         
           
             
               
                 
                   
                     P 
                     
                       DBV 
                       , 
                       i 
                     
                   
                   = 
                   
                     1 
                     - 
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           0 
                         
                         
                           r 
                           i 
                         
                       
                        
                       
                         
                           ( 
                           
                             
                               
                                 
                                   
                                     N 
                                     i 
                                   
                                   + 
                                   i 
                                   - 
                                   2 
                                 
                               
                             
                             
                               
                                 i 
                               
                             
                           
                           ) 
                         
                          
                         
                           
                             
                               p 
                               i 
                             
                              
                             
                               ( 
                               
                                 1 
                                 - 
                                 p 
                               
                               ) 
                             
                           
                           
                             
                               N 
                               i 
                             
                             - 
                             1 
                           
                         
                       
                     
                   
                 
               
               
                 
                   [ 
                   
                     Equation 
                      
                     
                         
                     
                      
                     3 
                   
                   ] 
                 
               
             
           
         
       
     
         [0072]    In Equation 3, N i  represents the number of nodes for the flow i, and p represents the probability of an error occurring. 
         [0073]    Also, the condition for the processing capacity required when the new flow is accepted exceeding the maximum processing capacity of the node can be expressed as Equation 4 shown below. 
         [0000]      Σ ∀i∈V     n   2 s   i   /x   min,i &lt;1   [Equation 4]
 
         [0074]    In Equation 4, S i  represents the service time for each flow, V n  represents the set of traffic flows transmitted initially, and x min,i  represents the minimum interval between arriving packets for each flow. 
         [0075]    In a multi-queue  404 , the packets that are to be processed may be inputted and placed in a standby state.  FIG. 5  illustrates the structure of a multi-queue  404  according to an embodiment of the invention. 
         [0076]    Referring to  FIG. 5 , a multi-queue  404  according to an embodiment of the invention may include a retransmission packet queue  500  and an initial transmission packet queue  502 . 
         [0077]    The retransmission packet queue  500  may be a queue for packets that have experienced a failure in transmission and are to be retransmitted, and the initial transmission packet queue  502  may be queue for packets that are being transmitted for the first time from a source node. The retransmission packet queue  500  can also include packets for which the local time was used up during standby in the initial transmission packet queue  502 . 
         [0078]    One reason for having the packet transmission scheduling device according to an embodiment of the invention place the retransmitted packets and initially transmitted packets in different queues is that the scheduler  406  may transmit the packets with different priority levels assigned for each queue. 
         [0079]    The packets waiting in the retransmission packet queue  500  may be assigned higher priority levels compared to the packets waiting in the initial transmission packet queue  502 . 
         [0080]    The scheduler  406  may determine the transmission order of the packets according to the priority levels of the packets placed in standby in the queues, and may provide the input/output interface unit with the packets that are to be transmitted. 
         [0081]    As described above, the scheduler  406  may assign higher priority to packets that are being retransmitted (i.e. packets waiting in the retransmission packet queue  500 ) compared to packets that are transmitted for the first time (i.e. packets waiting in the initial transmission packet queue  502 ). 
         [0082]    The packets standing by in the retransmission packet queue  500  may be packets for which the local times have been used up, and as such, the priority levels for the packets standing by in the retransmission packet queue  500  may be set based on the remaining ARQ times. 
         [0083]    The priority levels for the packets standing by in the initial transmission packet queue  502  may be set based on the local times. 
         [0084]      FIG. 6  is a flowchart illustrating the flow of a method for scheduling packet transmission according to an embodiment of the invention. 
         [0085]    Referring to  FIG. 6 , a packet may first be received at a device for scheduling packet transmission (operation  600 ). 
         [0086]    When a packet is received, it may be determined whether or not it is a packet from a new flow (operation  602 ). If it is a packet from a new flow, the CAC controller  424  may determine whether or not the packet from the new flow is to be accepted (operation  604 ). As described above, the determining of whether or not the packet from a new flow is to be accepted may consider the probability of delay bound violation and the node&#39;s processing capacity. 
         [0087]    If the probability of delay bound violation exceeds a preset threshold or if the processing capacity exceeds the maximum processing capacity of the node, the packet from the flow may be refused (operation  606 ). 
         [0088]    If the packet is not from a new flow, it may be determined whether the packet is a retransmitted packet or an initially transmitted packet (operation  607 ). 
         [0089]    If it is an initially transmitted packet, the packet may be inputted to the initial transmission packet queue (operation  608 ), and if it is a retransmitted packet, the packet may be inputted to the retransmission packet queue (operation  622 ). 
         [0090]    Once the packet is inputted to a queue, the local time and the ARQ time of the packet may be computed continuously (operation  610 ). 
         [0091]    If all of the local time is used up while in the initial transmission packet queue (operation  612 ), then the packet for which the local time has been used up may be inputted to the retransmission packet queue (operation  622 ). 
         [0092]    In the case of an initially transmitted packet, it may be determined whether or not the packet has the shortest local time from among the packets standing by in the initial transmission packet queue (operation  614 ). 
         [0093]    If it has the shortest local time, then the packet may be transmitted (operation  616 ). Then, after the packet transmission, it may be determined whether or not the transmission was successful (operation  618 ). 
         [0094]    If the packet does not have the shortest local time or if a failure occurs during transmission, then the packet may maintain its standby state in the queue (operation  620 ). 
         [0095]    As described above, if a received packet is not an initially transmitted packet, or even though it is an initially transmitted packet, if all of the local time has been used up while in the initial transmission packet queue, then the packet may be inputted to the retransmission packet queue (operation  622 ). 
         [0096]    For a packet waiting in the retransmission packet queue, it may be determined whether or not the ARQ time is greater than 0 (operation  624 ). If the ARQ time of the packet is 0 or less, then the packet may be dropped (operation  626 ). 
         [0097]    In the retransmission packet queue, the priority levels may be set by using the ARQ times, and hence it may be determined whether or not a packet has the shortest ARQ time from among the packets standing by in the retransmission packet queue (operation  628 ). If it has the shortest ARQ time, then the packet may be transmitted (operation  630 ). 
         [0098]    It may then be determined whether or not the packet was transmitted successfully (operation  632 ), and if the transmission of the packet was not successful or if the packet does not have the shortest ARQ time, the packet may maintain its standby state in the retransmission packet queue (operation  634 ). 
         [0099]    While the present invention has been described above using particular examples, including specific elements, by way of limited embodiments and drawings, it is to be appreciated that these are provided merely to aid the overall understanding of the present invention, the present invention is not to be limited to the embodiments above, and various modifications and alterations can be made from the disclosures above by a person having ordinary skill in the technical field to which the present invention pertains. Therefore, the spirit of the present invention must not be limited to the embodiments described herein, and the scope of the present invention must be regarded as encompassing not only the claims set forth below, but also their equivalents and variations.