WO1999057840A1

WO1999057840A1 - Method and means for processing information

Info

Publication number: WO1999057840A1
Application number: PCT/SE1999/000611
Authority: WO
Inventors: Lars Erik Westerberg; Håkan Gunnar OLOFSSON
Original assignee: Telefonaktiebolaget LM Ericsson AB
Current assignee: Telefonaktiebolaget LM Ericsson AB
Priority date: 1998-04-30
Filing date: 1999-04-16
Publication date: 1999-11-11
Anticipated expiration: 2000-10-30
Also published as: GB2352946B; GB2352946A; CA2330848A1; AU4400799A; GB0026223D0; CN1308800A; SE512310C2; SE9801529L; SE512310C3; DE19983161T1; SE9801529D0

Abstract

The present invention relates to methods and means for processing data frames in a packet data radio system. Data frames (A1, B1-B2) with specified time out periods are submitted to a second protocol layer (PL2) and segmented into radio blocks (Rb) which are transmitted to users (A, B) over a radio link (L). Radio blocks (Rb) not correctly received are re-transmitted. The number of re-transmissions is recorded to calculate the BLER. A transmission time for each data frame (A1, B1-B2) in the second protocol layer (PL2) is estimated. Data frames (A1, B1-B2) with transmission times exceeding a remaining time of their respective time out periods are flushed. The remaining data frames are scheduled to minimise the number of time outs before they are transmitted. The flushed data frames are re-submitted from a first protocol layer (PL1) to the second protocol layer (PL2).

Description

1 METHOD AND MEANS FOR PROCESSING INFORMATION

TECHNICAL FIELD OF THE INVENTION

The present invention relates to methods and means for processing data frames in a packet data radio system.

DESCRIPTION OF RELATED ART

By "radio unit" is meant all portable and non-portable equipment intended for radio communication, like mobile phones, transceivers, pagers, telex, electronic notebooks, laptops with integrated radios, communicators, computers, routers, tailored icrocnips connecting to radios or any other electronic equipment using a radio link as a mean of communication. These equipments can be used in any type of radio communication system, such as cellular networks, satellite or small local networks.

In a new generation of wireless data communication services, e.g., GPRS (General Packet Radio Service) in GSM, data packets are transferred across a radio interface. Typically, several users share one or more physical radio channels, and the network is confronted with the delicate task of processing the transfer of data packets in a way that optimizes the overall performance of the system. The situation is complicated by the fact that even though different users share the same physical medium, the probability of successfully transferring a data packet across the radio interface is different for different users. This is due to local conditions, e.g., geographical location, coding and output powers used.

A known successful architecture in cellular radio systems is to divide the system into a switching system (SS) and a base station system (BSS). Schematically, the SS is responsible for switching traffic to the intended BSS destination but does not need to know which radio protocols are utilized, or how the physical (radio) resources are used. In contrast, the BSS is ignorant about the overall network and switching structure. The BSS simply receives addressed data entities from the SS, and uses its radio resources, as it seems fit to transfer the received entities to the correct address. The benefit of this separation into SS and BSS parts is that one part can be improved, or even replaced, without affecting the other.

In for instance a GPRS-system, incoming data packets (e.g. IP packets) are in an LLC protocol layer in the SS segmented into smaller data packets, "LLC frames". The LLC frames are then addressed and submitted to an RLC protocol layer in the BSS where the LLC frames are segmented into smaller data units, "RLC blocks". The RLC blocks are transferred one by one across a radio link to a radio unit. When all RLC blocks in an LLC frame have been successfully received by the radio unit, the LLC frame is reconstructed in an RLC protocol layer in the radio unit and passed on to an LLC protocol layer in the radio unit. When a radio unit has received a complete and correct LLC frame, an acknowledgment is sent back to the LLC protocol layer in the SS.

An LLC frame that is not acknowledged within a stipulated time (in GPRS typically 3 seconds) is regarded as lost and is re- submitted to the BSS from the SS. Likewise, an LLC frame that is negatively acknowledged by the radio unit is re-transmitted from the BSS to the radio unit.

From a user perspective, the total throughput is the number of LLC frames successfully transferred across the GPRS system per unit time.

Existing data packets processing methods are based on quality of service, data packet arrival times and possibly data packet deadlines that are allocated to data packets based on the associated quality of service. These processing methods do not consider the two-level protocol structure (with an LLC protocol layer and an RLC protocol layer) in a GPRS-like system.

The existing art in a GPRS-like radio data system does not fully optimize the use of the radio resources, which leads to a poor throughput.

The US patent 5440545 describes a packet switching system and a method for acknowledging receipt of a plurality of packet fragments. A source device allocates additional bandwidth resources in order to re-transmit packet fragments that have been lost or corrupted during the first transmission.

The US patent 5515385 describes a device and a method for limiting the delay in a communication system by eliminating the risk for duplicate data frames.

The US patent 5487068 describes a method for reducing transmission delays in a packet-switched data communication system by eliminating the need to make an additional request to allocate a channel when a retransmission of segments is needed.

As will be seen herein, each of the device and methods disclosed in these patents is of different types and construction than the methods and means of the present invention.

SUMMARY

The present invention meets some problems related to optimising the processing of framed packet data where a data frame comprises of a number of data blocks.

One problem occurs when a data frame which is being transmitted to a user/system across a radio link times out before it is completely transmitted.

Another problem occurs when data blocks which have been transmitted to a user/system across a radio interface a first time have to be re-transmitted again over the radio link when the associated data frame times out.

In light of the foregoing, a primary object of the present invention is to provide methods and means for processing data blocks in a packet data radio system.

Another object of the present invention is to provide methods and means for efficiently utilising the bandwidth of the system.

Still another object is to process the data blocks in a packet data radio system in such a manner that a maximum number of the corresponding data frames transferred across a radio interface are acknowledged before they time out.

Yet another object of the present invention is to minimise the number of unnecessary re-transmissions over a radio link due to time outs of data frames .

In a method according to the present invention a transmission time to completely transmit a data frame over a radio link is estimated and this information is used to judge if the data frame can be completely transmitted before it times out. The method also uses said information to schedule the order in which the data frames are to be transmitted. According to one embodiment of the method a second protocol layer transmits data frames to a user. The Block Error Rate (BLER) is measured in the second protocol layer by recording what fraction of the radio blocks transmitted to the user that have to be re-transmitted. Using this information, and information about the radio resources to be allocated for the transmission, the transmission time for each data frame stored in or under transmission from the second protocol layer is estimated. If the estimated transmission time of any data frame is larger than a remaining time of a time out period of that data frame, that data frame shall be flushed in the second protocol layer. The transmission of the remaining data frames from the second protocol layer are scheduled to minimise the number of data frames that time out in the second protocol layer. In accordance with a re-transmission protocol of a first protocol layer, the first protocol layer re-submits a new data frame, identical to the flushed data frame, to the second protocol layer.

A system and a radio unit comprise means for utilising the method according to the present invention.

According to one embodiment of the radio unit, the radio unit comprises means for: estimating radio resources to be allocated for transmissions; measuring the Block Error Rate (BLER) ; estimating the transmission time for each data frame in the second protocol layer in the radio unit; detecting in advance if time outs will occur; and scheduling the order in which the data frames are to be transmitted from the radio unit. If a time out for a data frame is detected in advance, the radio unit has means to immediately stop and flush that data frame.

According to one embodiment of the system, the system comprises means for: estimating radio resources to be allocated for transmissions; measuring the Block Error Rate (BLER); estimating the transmission time for each data frame in the second protocol layer in the system; scheduling the order in which the data frames are to be transmitted from the system; and detecting in advance if a time out will occur. If a time out is detected in advance for a data frame, the system has means to immediately stop and flush that data frame.

An advantage with the present invention is that radio resources are not wasted on data frames that are estimated to time out and to be re-transmitted anyway. Thus, the bandwidth of the system is more often used for useful transmission, which in turn increases data throughput and reduces delay.

Another advantage is that the transmission is less sensitive to periodical interference which can completely block a connection to a user, hence causing long delays to other users in the system.

Yet another advantage is that the risk of transmitting the same data frame twice due to re-submission to a second protocol layer of a data frame that is anyway being transmitted the first time is eliminated.

BRIEF DESCRIPTION OF THE DRAWINGS

Figure 1 is a view of a block diagram of a GPRS system.

Figure 2 is illustrating an LLC frame segmented into a number of RLC blocks.

Figures 3a-c are illustrating an example of a known data frame processing scenario.

Figures 4a-b are illustrating a flow chart of a first embodiment of a method according to the present invention.

Figures 5a-d are illustrating a data frame processing scenario utilising the first embodiment of the method according to figures 4a-b.

Figures 6a-b are illustrating a flow chart of a third embodiment of a method according to the present invention.

Figure 7 is illustrating a block diagram of an embodiment of means according to the present invention.

DETAILED DESCRIPTION OF EMBODIMENTS

The present invention relates to methods and means for processing data frames in a packet data radio system in a way that leads to an efficient use of the radio resources and a good throughput.

The packet data radio system shall preferably comprise a protocol layered structure, where in a specified layer, a first packet data unit submitted to the specified layer is further segmented (divided) into smaller second packet data units before transmission over a radio link to a user/system. The first packet data unit submitted to the specified layer is resubmitted to that specified layer if it is not acknowledged to have been correctly received by the user/system within a stipulated time.

The packet data radio system can as an example comprise a first sub-system and a second sub-system serving a number of users with radio units, where the first sub-system, the second subsystem and the radio units comprise a first and a second protocol layer.

Figure 1 illustrates a schematic block diagram of a GPRS system 100 which is an example of a packet data radio system comprising an LLC protocol layer PL1 as the first protocol layer, and an RLC protocol layer PL2 as the second protocol layer (LLC = Logical Link Control and RLC = Radio Link Control) .

The GPRS system 100 in this example comprise a switching system SS, a base station system BSS and a number of users A-C with radio units RU1-RU3.

The LLC and RLC protocol layers PL1, PL2 respectively in radio unit RU2 and RU3 are not illustrated in figure 1.

At least one radio link L is used for radio transmissions between the base station system BSS and the users A-C. The base station system BSS is connected to the switching system SS via a trunk line Tl. The switching system SS can as an example be connected via a trunk line T2 to a fixed data communications network, e.g. an Intranet, the Internet, or to the public switched telephone network (PSTN) .

In the GPRS system 100, incoming data packets (e.g. IP packets) over the trunk line T2 to the SS are segmented into data frames (LLC frames) of maximum length 1.5 Kbytes. The LLC frames are processed in the LLC protocol layer PLl within the SS. The LLC frames are submitted over the trunk line Tl to the RLC protocol layer PL2 in the BSS where they are segmented into data blocks, RLC blocks. The number of RLC blocks comprising an LLC frame depends on the size of the LLC frame and the (radio block) coding used. In GPRS, an LLC frame is typically segmented into 30 to 80 RLC blocks. The RLC blocks are fit to be transferred one by one across the radio link L.

The LLC protocol layer, defined in the technical specifications for GPRS TS GSM 04.64, is a protocol layer that works between a switching node and a radio unit. In one aspect of GPRS, the LLC protocol layer segments, and addresses incoming data packets from any application using GPRS (e.g., TCP/IP) to LLC packet data units ("LLC frames") . The LLC protocol layer then uses more primitive radio interface protocols, e.g. an RLC protocol, as a bearer service for transporting the LLC frames to the peer LLC logical unit in the radio unit. In the LLC protocol layer of the radio unit, the LLC frames are received, the application data units are reconstructed and forwarded to the application. The LLC protocol layer can run in acknowledge mode, in which case each LLC frame is acknowledged at successful reception in the receiving end. In this mode, LLC frames that have not been acknowledged to the sending side within a stipulated time are said to time out, and are retransmitted to the receiving side.

The RLC protocol layer, defined in the technical specifications for GPRS TS GSM 04.60, is a protocol layer that works between a 10

BSS node and the radio unit. In one aspect of GPRS, the RLC protocol layer segments, and addresses LLC frames received from the LLC protocol layer into radio blocks ("RLC blocks") . The radio blocks are then transmitted over the radio interface, possibly using an acknowledgement mechanism in the RLC protocol. In a receiving radio unit, the RLC protocol layer is responsible for reconstructing the LLC frames and for forwarding the LLC frames to the LLC protocol layer in that unit .

Figure 2 shows an illustration of radio blocks Rb belonging to a segmented LLC frame Lf in a packet data radio system, e.g. a GPRS system. The LLC frame Lf and its radio blocks Rb is an example of a data frame comprising a number of data blocks.

Figures 3a-c show an illustration of an example of a data frame processing scenario according to prior art utilised in the GPRS system 100 according to figure 1. The details of the SS, the first protocol layer PLl, user C and the radio units of user A, B, C respectively are not shown in these figures. The users A and B share one radio link L with a capacity of 50 radio blocks per second.

The block error rate (BLER) is 25% for both users. An ARQ (Automatic Repeat Request) protocol is used, so that a radio block that is not received correctly by a radio unit in the system is re-transmitted. The LLC frames Al and B1-B2 have a time-out period that is set to 3 seconds. If the SS does not receive an acknowledgement from the BSS within 3 seconds from that an LLC frame is submitted from the SS to the BBS, that LLC frame will be resubmitted to the BSS.

Points of time T are introduced in the text below to make the description of the scenario more clear and easy to understand. The points of time T are not shown in the figures. 11

According to figure 3a (T=0) , the BSS is busy transmitting an LLC frame Bl, one radio block Rb at the time, to user B over the radio link L. The RLC protocol layer PL2 in the BSS receives an LLC frame Al addressed to user A from the SS. The LLC frame Al is stored and segmented into 60 radio blocks in the RLC protocol layer PL2. The radio blocks are not shown in the figure.

At completion of the transfer of the LLC frame Bl, according to figure 3b (T=1.6 seconds), the BSS starts to transmit the LLC frame Al, one radio block Rb at the time, to user A over the radio link L. At the same time, following the acknowledgement from an LLC protocol layer in the radio unit of user B to the SS of a successfully transmitted LLC frame Bl to user B, a second LLC frame B2 to user B is submitted to the RLC protocol layer PL2 in the BSS from the SS .

With a BLER of 25%, it will take 80 radio blocks to complete the transfer of the LLC frame Al .

According to figure 3c (T=3.0 seconds), the BSS is still busy transmitting the LLC frame Al . Three seconds have now passed since the LLC frame Al was submitted from the SS to the RLC protocol layer PL2 in the BSS, and no acknowledgement of Al has been sent to the SS. In accordance with the GPRS protocol, the time out period of 3 seconds for the LLC frame Al has elapsed

(timed out) . The remaining radio blocks Rb in the RLC protocol layer PL2 in the BSS belonging to the LLC frame Al are flushed (deleted) . The LLC frame Al is re-submitted to the RLC protocol layer PL2 in the BSS from the SS and stored. The flushed data frame Al is marked with an X in the figure. The BSS starts to transmit the LLC frame B2 to user B.

The only useful radio blocks that have been transmitted across the radio interface at the period of time T=3 seconds are those belonging to the LLC frame Bl, see user B in figure 3c. Useful radio blocks are defined as undamaged radio blocks belonging to 12 complete LLC frames forwarded to a radio unit. No radio block from the LLC frame Al is useful, since the LLC frame Al is not transmitted across the radio link L in its completeness. The LLC frame Al has to be re-transmitted.

In the example, both users A and B experience a BLER of 25%, meaning that on the average 25% of the radio blocks have to be re-transmitted over the radio link L. This makes the maximum effective throughput over the radio link 75% of the full link capacity. With prior art according to figure 3a-c, 60 out of 150 radio blocks transmitted between T=0 and T=3 seconds are useful, which leads to a throughput of 40% during that period of time. This is largely due to the waste of radio resources on LLC frames that time out (in the example the LLC frame Al ) .

Figures 4a-b illustrates a flow chart of a first embodiment of the method according to the present invention for processing data frames in a packet data radio system comprising the LLC protocol layer PLl and the RLC protocol layer PL2. The LLC protocol layer PLl and the RLC protocol layer PL2 are examples of a first and a second protocol layer.

Some of the steps in the first embodiment will also be described in conjunction with figures 5a-d below where the method is utilised in a data frame processing scenario.

According to a step 401a in figure 4a, the LLC protocol layer PLl in the SS submits new LLC frames to the RLC protocol layer PL2 in the BSS.

According to a step 401b, the RLC protocol layer PL2 segments each LLC frame into a number of radio blocks, e.g. 50 radio blocks, and stores the LLC frames in the same order as they are received.

According to a step 402a, the LLC protocol layer PLl re-submits previously timed out LLC frames (see step 407 and 410) to the RLC protocol layer PL2. 13

According to a step 402b, the RLC protocol layer PL2 segments and stores the re-submitted LLC frames together with the new LLC frames .

According to a step 403, the RLC protocol layer PL2 estimates the radio resources to be allocated over a period of time, e.g. 3 seconds, for transmission of each LLC frame stored in the RLC protocol layer PL2.

According to a step 404, the RLC protocol layer PL2 estimates a remaining transmission time for each LLC frame presently being transmitted from the RLC protocol layer. The remaining transmission time is the time to successfully transmit all remaining RLC blocks m the BSS belonging to an LLC frame under transmission. The LLC frames are transmitted one RLC block at the time. The BSS can as an example use previously acquired information about the BLER, new information about the BLER (see step 415) and the estimated radio resources according to step 403 to estimate the remaining transmission time.

If, according to a step 405, an LLC frame has an estimated remaining transmission t me exceeding a remaining t me of its time out period, the LLC frame is detected in advance to time out (i.e., the detection of the impending time out is done before the actual time out occurs) and the method continues with a step 406.

If, according to step 405, no time out is detected m advance, the method continues to transmit remaining data blocks of the LLC frame under transmission and continues with a step 408.

According to step 406, the RLC protocol layer PL2 interrupts the transmission of the LLC frame detected in advance to time out (step 405) before any more RLC blocks belonging to that LLC frame are transmitted. 14

According to a step 407, the RLC protocol layer PL2 flushes

(deletes) all the remaining RLC blocks belonging to the LLC frame detected to be timed out in step 405. The method continues with step 408.

According to the step 408, the RLC protocol layer PL2 estimates a transmission time for each LLC frame presently being stored in the RLC protocol layer. The transmission time for an LLC frame is the time it would take to successfully transmit over the radio link L, all the RLC blocks comprising that LLC frame. As in step 404, previously acquired information about the BLER (Block Error Rate), new information about the BLER (see step 415) and the estimated radio resources according to step 404 is used to estimate the transmission time.

If, according to a step 409 in figure 4b, a stored LLC frame has an estimated transmission time exceeding its time out period, that LLC frame is detected in advance to time out and the method continues with a step 410.

If, according to step 409, no time out is detected in advance, the method continues with a step 411.

According to step 410, the RLC protocol layer PL2 flushes (deletes) all the LLC frames that in step 409 are detected to time out. The method continues with step 411.

According to step 411, the RLC protocol layer PL2 schedules the order in which the stored LLC frames will be transmitted to their respective user. The scheduling is made in such a way that a maximum number of the LLC frames in the RLC protocol layer are going to be transmitted in their completeness before they time out. The method uses the estimated transmission times acquired in step 408 and the remaining time of the LLC frames time out periods to schedule the stored LLC frames. 15

According to a step 412, the RLC protocol layer PL2 transmits one or more RLC blocks belonging to one or more LLC frames to one or more users according to the scheduling in step 411.

According to a step 413a, the RLC protocol layer PL2 receives an ACK or NACK for each one of the RLC blocks transmitted according to step 412 (ACK = a positive acknowledge, NACK = a negative acknowledge according to the ARQ protocol) .

According to a step 413b, transmitted RLC blocks for which a NACK is received are re-transmitted according to known ARQ protocols .

According to a step 414, the RLC protocol layer PL2 records the number of re-transmissions needed to transmit each radio block.

According to a step 415, the RLC protocol layer PL2 calculates the BLER for each transmission where an ACK or NACK according to step 413a is received, by using the number of retransmissions recorded in step 414. These BLER values are then used in step 404 and 408 to estimate the transmission times.

In a second embodiment of the method according to the present invention, not illustrated in any figure, a negative acknowledgement is transmitted from the RLC protocol layer PL2 to the LLC protocol layer PLl after an LLC frame is detected in advance to time out and flushed according to step 407 or step 410. An identical LLC frame to the flushed LLC frame is re-submitted from the LLC protocol layer PLl to the RLC protocol layer PL2 immediately after the negative acknowledgement is received due to the flushed LLC frame. The method continues as in the first embodiment in figure 4a-b with step 408 or step 411.

Figures 5a-d show an illustration of a data frame processing scenario where the first embodiment of the method according to 16 figures 4a-b is utilised. The scenario is identical to that in figure 3. References are made both to figures 5a-d and to the corresponding steps in figure 4a-b.

Points of time T are introduced in the text below to make the description of the scenario more clear and easy to understand. The points of time T are not shown in the figures.

According to figure 5a (T=0), the RLC protocol layer PL2 has received, according to step 401a, the new LLC frame Al from the LLC protocol layer PLl. The RLC protocol layer PL2 segments the LLC frame Al into 60 radio blocks according to step 401b. The RLC protocol layer PL2 is busy transmitting the LLC frame Bl, one radio block Rb at the time, to user B according to step 412.

According to figure 5b (T=1.6 seconds), the transmission of the LLC frame Bl to user B is completed.

Following an acknowledgement from user B of the successfully transmitted LLC frame Bl, the LLC protocol layer PLl submits the LLC frame B2 to the RLC protocol layer PL2, according to step 401a. The LLC frame B2 is segmented into 60 radio blocks and stored in the RLC protocol layer PL2, according to step 401b. There are now two LLC frames (Al and B2), stored in the RLC protocol layer PL2. No timed out LLC frame is submitted according to step 402a. The RLC protocol layer PL2 estimates the radio resources to be one GPRS channel, corresponding to a bare bandwidth of 50 radio blocks per second, according to step 403.

No LLC frame is presently being transmitted, and the method proceeds to step 408 where the RLC protocol layer PL2 estimates the transmission times of the stored LLC frames Al and B2. During the previous transmission of the LLC frame Bl, the BLER of user B was measured to 25%, and hence the RLC protocol layer PL2 estimates the transmission time of B2 to be 1.6 seconds (80 radio blocks, including 25% re-transmissions) . No BLER-related information is available for user A, so the transmission time 17 for Al is optimistically estimated to 1.2 seconds (60 radio blocks, no re-transmissions).

The time remaining before time outs occur, are for Al and B2 1.4 seconds and 3.0 seconds respectively. These are larger than the estimated transmission times, hence no time out is detected in advance in step 409.

In step 411, the LLC frame Al is scheduled for immediate transmission, and the LLC frame B2 is scheduled to follow. With this scheduling, according to the estimated transmission times in step 408, both Al and B2 will be transmitted in their completeness before their respective time outs.

The method proceeds with steps 412-415, where the RLC protocol layer starts to transmit the LLC frame Al, one radio block Rb at the time, to user A over the radio link L. ACK/NACK information for each transmitted RLC block is received from user A. The RLC protocol layer PL2 records the number of retransmissions and calculates the BLER.

According to the scenario in figure 5c (T=1.84 seconds) 12 radio blocks of the LLC frame Al have been transmitted. With an actual BLER of 25%, 9 of the 12 radio blocks have been correctly received, while 3 have been damaged when transmitted over the radio link L. Based on this success rate, the RLC protocol layer PL2 have calculated the BLER for user A to be 25%.

The method once again follows the flow diagram in figure 4a-b. No new LLC frames are submitted according to steps 401a and 402a. In step 403, the radio resources are once more estimated to be 50 radio blocks per second.

With a BLER of 25% for user A, the estimated transmission time, according to step 404, for the 51 remaining radio blocks belonging to the LLC frame Al under transmission is 1.36 seconds. Since the remaining time of the time out period for 18 the LLC frame Al is now 1.16 seconds, a time out of the LLC frame Al is detected (in advance) in step 405.

The transmission of the LLC frame Al is interrupted, and the remaining radio blocks in PL2 belonging to the LLC frame Al are flushed according to step 406 and 407 respectively. The flushed part of the LLC frame Al in the RLC protocol layer PL2 is marked with an X in figure 5c.

In step 408, the transmission time of the stored LLC frame B2 is again estimated to 1.6 seconds. Since the remaining time of its time out period is 2.76 seconds, there is no time out of the LLC frame B2 detected in step 409. With only the LLC frame B2 stored in the RLC protocol layer PL2, the scheduling in step 411 is trivial, and the method proceeds with steps 412-415 to transmit RLC blocks belonging to the LLC frame B2.

According to the scenario in figure 5d (T=3 seconds), the BSS is busy transmitting the LLC frame B2. Three seconds have now passed since the LLC protocol layer PLl submitted the LLC frame Al to the RLC protocol layer PL2. User A has not received the LLC frame Al (which was flushed at T=1.84 seconds, see figure 5c) , and accordingly, no acknowledgement-of-reception of the LLC frame Al has been transmitted from user A to the LLC protocol layer PLl. The time out period of 3 seconds for the acknowledgement of the LLC frame Al has elapsed (timed out) , and consequently the LLC frame Al is re-submitted to the RLC protocol PL2 according to step 402a.

The useful radio blocks that have been transmitted across the radio link are those belonging to the LLC frame Bl and B2 (provided that the remaining radio blocks of the LLC frame B2 in figure 5d are completely transmitted within the next 1.6 seconds) to user B.

Out of the total of 150 radio blocks transmitted during the 3 second period depicted in figures 5a-d, with 25% BLER, 75% of the 138 radio blocks transmitted to user B contributed to the 19 throughput. The throughput is hence 67%, which is to be compared to the throughput of 40% in the same scenario using prior art in figure 3a-c. The improvement is entirely due to the inventive method, which enables the BSS to stop the transfer of Al .

The Block Error Rate (BLER) is an example of a transmission parameter the RLC protocol layer PL2 can use to estimate the transmission time to successfully transmit a stored LLC frame, according to step 408 in figure 4a, or an LLC frame presently being transmitted, according to step 404.

As previously mentioned, the BLER for a user/system is calculated by recording what fraction of the radio blocks transmitted over the radio link L to a user/system have to be re-transmitted, according to step 414. The method can as an example use the BLER of the latest transmitted LLC frame or radio block over the radio link L or an average value of the BLER of a number of previous transmitted LLC frames or radio blocks . The transmission time can as an example be calculated as (time to transmit one block) x (number of remaining blocks) / (1-BLER) .

Other examples of transmission parameters an RLC protocol layer PL2 can use to estimate the transmission time according to step 404 and step 408 in figure 4a are the bit error rate (BER) , and the cell average of BLER and BER. A lower bound on the transmission time for any given LLC frame is always given by the number of remaining radio blocks of that LLC frame divided by the bare capacity of the packet data radio system (radio blocks/second) in that cell.

If no current information about the BLER, BER or time delays is available, e.g. after a long break in the transmission over the radio link L, the RLC protocol layer can use, e.g. an old BLER value, a measured cell average or a fixed default value. 20

The first and second embodiment of the method have been described for a down-link transmission, see figure 5a-d, where at least one user with a radio unit is a receiver of transmitted LLC frames from a BSS. The methods can also be applied on an up-link transmission where a BSS is a receiver of transmitted LLC frames from at least one radio unit.

The method according to figure 4a-b can be applied on an up-link transmission where a radio unit schedules the transmission of its LLC frames in a situation where the LLC frames belong to different data flows.

One example of such a situation is when a user is running several applications simultaneously over one GPRS channel, so that LLC frames belonging to different data flows compete for resources on the radio link L.

Another example of such a situation is when several users are sharing one radio unit. The radio unit schedule the LLC frames of the different users over the (by the BSS) allocated up-link resources .

The main difference from the down-link transmission is that only one radio link L is used, so that the estimated BLER is identical for all users.

A radio unit for utilising the first and second embodiment of the method can as an example comprise an LLC layer as the first protocol layer and an RLC protocol layer as the second protocol layer. On top of the LLC layer, one or more applications can run in parallel.

The method according to figure 4a-b can also be applied on an up-link transmission where the BSS schedules up-link transfers from different radio units, i.e. determines which user shall access the radio link for up-link transmission. 21

Figures 6a-b illustrates a flow chart of a third embodiment of the method according to the present invention for processing data frames in a packet data radio system, where the BSS schedules up-link transmissions from different radio units. The up-link workflow according to figures 6a-b runs in the BSS which needs exactly the same information regarding the up-link transmissions as it does regarding the down-link transmissions illustrated in figure 4a-b.

According to a step 601, the BSS receives information (about length and time to time-out) from the radio units for new data frames submitted to the RLC protocol layer PL2 in each radio unit .

According to a step 602, the BSS receives information (about length and time to time-out) from the radio units about previously timed out data frames that are being re-submitted to the RLC protocol layer PL2 in each radio unit.

Step 603-605 are the same as step 403-405 respectively according to figure 4a. In case of a detected time out in step 605 the BSS instructs the radio unit in a step 606 to interrupt the transmission of the LLC frame to be timed out. This automatically induces a flush of that LLC frame in the radio unit at the time of time-out.

Alternatively, at the detection of a frame from a user/system to time out in step 605, the BSS may simply not allocate radio resources to that user/system until the frame has indeed timed out. Also this will induce a flush and a re-submissions of the frame to PLl in the radio unit.

According to a step 607, the BSS estimates transmission times for data frames stored in the RLC protocol layer in each radio unit. The estimation is made in the same way as in step 408 according to figure 4a. 22

According to a step 608, the BSS schedules the transfers of the data frames stored in each radio unit. The scheduling is made in the same way as in step 411 according to figure 4b.

According to a step 609, the BSS instructs each radio unit to transmit one or more data blocks from scheduled data frames.

According to a step 610, the RLC protocol layer PL2 in each radio unit re-transmit damage radio blocks to the BSS.

According to a step 611, the BSS records the number of damaged radio blocks received from the radio units.

According to a step 612, the BSS calculates the BLER of the transmissions from each radio unit. The calculation is made in the same way as in step 415 according to figure 4b.

The crucial difference in the up-link transmission according to figures 6a-b as compared to the down-link transmission in figures 4a-b is that for each LLC frame submitted to the RLC protocol layer PL2 in each radio unit, information about the LLC frame length and time to time out have to be reported to the BSS.

The methods according to the present invention may be repeated automatically to give a continuos re-evaluation of which LLC frame to transmit next. As an example the methods can be repeated once every 240ms.

The methods may as an alternative be event-initiated, e.g. the arrival of an LLC frame to the RLC protocol layer PL2 or after a determined number of transmitted radio blocks Rb .

Figure 7 illustrates a block diagram of an embodiment of means 700 for utilising the method according to the present invention.

A radio resource estimator 701, to allocate radio resources for transmission of LLC frames, is connected to a transmission time 23 estimator 702, for estimating the transmission times for the LLC frames .

The transmission time estimator 702 is connected to a frame deleting unit 703 and a scheduler 704.

The frame deleting unit 703 is arranged to detect in advance if a time out occurs, interrupt the transmission of LLC frames and flush LLC frames. The frame deleting unit 703 can also as an alternative transmit negative acknowledgements to a frame submitting unit 709 when data frames are detected in advance to time out. The frame deleting unit 703 is connected to a queue device 705.

The frame submitting unit 709 is also connected to the queue device 705. The frame submitting unit 709 is arranged to submit data frames to the queue device 705 and to re-submit identical data frames to flushed data frames when the time out periods for the flushed data frames have elapsed and/or when a negative acknowledgement is received from the frame deleting unit 703.

The scheduler 704, for determining the order in which the LLC frames are going to be transmitted from the queue device 705, is also connected to the queue device 705.

The queue device 705, in which the LLC frames to be transmitted are stored in a queue and segmented into RLC blocks, is connected to a transmitter 706, for transmitting and retransmitting RLC blocks.

A receiver 707, arranged to receive ACK/NACK signals, is connected to a link quality estimator 708, which records the number of re-transmissions needed to successfully transmit each RLC block and calculates the BLER. The link quality estimator 708 is connected to the transmission time estimator 702. 24

The invention can be completely or partially implemented as software in at least one microprocessor. As an example, the radio resource estimator 701, the transmission time estimator 702, the frame deleting unit 703, the scheduler 704, the queue device 705 and the link quality estimator 708 can be logical units in at least one computer system.

The packet data radio system described in conjunction with figure 4a-6b is a GPRS system comprising an LLC protocol layer PLl and an RLC protocol layer PL2. As mentioned before this is just one example of a packet data radio system where the invention can be utilised and one example of how such a system can be arranged. The invention applies to any packet data radio system that has a protocol layered structure.

A system or device in which the invention is utilised can be divided into any number of protocol layers, function blocks, units, sub-systems or similar to transfer packet data from one place to another.

As an example the switching system SS and the base station system BSS, according to figure 1, can be integrated in one single system.

Claims

25 CLAIMS

1. A method for processing data frames (Lf, Al, B1-B2) in a packet data radio system, where each of said data frames (Lf, Al, B1-B2) has a specified time out period for a complete transmission to a receiver (A, B, C, RU1-RU3, BSS) , said data frames (Lf, Al, B1-B2) being segmented into a number of data blocks (Rb) which are transmitted (412) one by one across a transmission medium to their respective receiver (A,B,C,RU1- RU3,BSS) , c h a r a c t e r i s e d in that the transmission time for at least one of said data frames (Lf, Al, B1-B2) is estimated (404,408,604,607) based on at least one transmission parameter to detect in advance if a time out will occur (405,409,605), where said data frame (Lf, Al, B1-B2) is determined in advance to time out if said estimated transmission time exceeds the remaining time of its time out period.

2. The method as claimed in claim 1, c h a r a c t e r i s e d in that the transmission order of said data frames (Lf, Al, B1-B2) is scheduled (411,608) in order for said data frames to be transmitted to their respective receiver (A,B, C, RU1-RU3,BSS) in such an order that the number of data frames to be timed out (Al) is minimised, where said scheduling (411,608) is based on said estimated transmission times (408,607) and said remaining time of said time out periods.

3. The method as claimed in claim 1 or 2, c h a r a c t e r i s e d in that a data frame (Al) detected in advance to time out (405,409,605) is flushed (407,410,606).

4. The method as claimed in one of claims 1-3, c h a r a c t e r i s e d in that if some of said data blocks (Rb) are not correctly received by said receiver (A,B,C,RU1-

RU3,BSS) they are re-transmitted (413b, 610) and that the number of re-transmissions needed to successfully transmit each data block (Rb) to its receiver (A, B, C, RU1-RU3, BSS) is recorded 26

(414,611), where said recorded number is used to calculate (415,612) said transmission parameter used when estimating (404,408,604,607) said transmission time.

5. The method as claimed m one of claims 1-4, c h a r a c t e r i s e d in that said estimated transmission time is the transmission time to successfully transmit all data blocks (Rb) belonging to one data frame (Lf, Al, B1-B2) .

6. The method as claimed in one of claims 1-5, c h a r a c t e r i s e d in that an identical data frame to said flushed data frame (Al) is re-submitted (402a) when said time out period for said flushed data frame (Al) has elapsed.

7. The method as claimed m one of claims 1-5, c h a r a c t e r i s e d in that a negative acknowledgement is transmitted if a data frame (Lf, Al, B1-B2) is detected in advance to be timed out.

8. The method as claimed in claim 7, c h a r a c t e r i s e d in that an identical data frame to said flushed data frame (Al) is re-submitted (402a) if said negative acknowledgement is received.

9. The method as claimed in one of claims 3-8, c h a r a c t e r i s e d in that said data frame (B2) which is flushed (410) is flushed before any of the data blocks (Rb) belonging to said data frame are transmitted.

10. The method as claimed in one of claims 1-9, c h a r a c t e r i s e d m that said method uses transmission parameters including a bit error rate when estimating (404,408,604,607) said transmission time.

11. The method as claimed m one of claims 1-10, c h a r a c t e r i s e d in that said method uses transmission parameters including a transmission delay time when estimating (404,408,604,607) said transmission time. 27

12. The method as claimed in one of claims 1-11, c h a r a c t e r i s e d in that said transmission medium is a radio link (L) .

13. The method as claimed in one of claims 1-12, c h a r a c t e r i s e d in that the transmission of a data frame (Al) under transmission which is detected in advance to time out (405,605) is interrupted (406,606).

14. The method as claimed in one of claims 1-13, c h a r a c t e r i s e d in that radio resources to be allocated for said transmission is estimated (403,603) .

15. The method as claimed in one of claims 1-14, c h a r a c t e r i s e d in that information about the length of said data frames (Lf, Al, B1-B2) and their time out periods are received (601,602).

16. The method as claimed in one of claims 1-15, c h a r a c t e r i s e d in that instructions regarding the order in which to transmit one or more data blocks from scheduled data frames are received (609) .

17. An arrangement for processing data frames (Lf, Al, B1-B2) in a packet data radio system, where each of said data frames (Lf,

Al, B1-B2) has a specified time out period for a complete transmission to a receiver (A, B, C, RU1-RU3, BSS) , said arrangement includes means for: storing (705) said data frames (Lf, Al, B1-B2); segmenting (705) said data frames (Lf, Al, B1-B2) into a number of data blocks (Rb) ; transmitting (706) said data frames (Lf, Al, B1-B2) across at least one radio link (L) to at least one receiver (A,B,C,RU1-

RU3,BSS); and re-transmitting (706) data blocks (Rb) not correctly received by said receiver (A, B, C, RU1-RU3, BSS) ; 28 c h a r a c t e r i s e d in that said arrangement comprises means for estimating (702) the transmission time for at least one of said data frames (Lf, Al, B1-B2) and means to detect (703) in advance if a time out will occur for any of said data frames (Lf, Al, B1-B2), where said estimating is based on at least one transmission parameter, and where said data frame (Lf, Al, B1-B2) is determined to be timed out in advance if said estimated transmission time exceeds the remaining time of its time out period.

18. The arrangement as claimed in claim 17, c h a r a c t e r i s e d in that said arrangement comprises means for scheduling (704) the transmission order of said data frames (Lf, Al, B1-B2) in order for said data frames to be transmitted to their respective receiver (A, B, C, RU1-RU3, BSS) in such an order that the number of data frames (Lf, Al, B1-B2) to be timed out is minimised, where said scheduling is based on said estimated transmission times and said remaining time of said time out periods .

19. The arrangement as claimed in claim 17 or 18, c h a r a c t e r i s e d in that said arrangement comprises means for flushing (703) said data frames (Al) detected in advance to be timed out.

20. The arrangement as claimed in one of claims 17-19, c h a r a c t e r i s e d in that said arrangement comprises means for recording (708) the number of re-transmissions needed to transmit each data block (Rb) to said receiver (A,B,C,RU1- RU3,BSS), and means to calculate (708) said transmission parameter used when estimating said transmission time by using said recorded number of re-transmissions.

21. The arrangement as claimed in one of claims 17-20, c h a r a c t e r i s e d in that said arrangement comprises means for interrupting (703) transmissions of data frames (Al) which are detected in advance to be timed out. 29

22. The arrangement as claimed in one of claims 17-21, c h a r a c t e r i s e d in that said arrangement comprises means for re-submitting (709) identical data frames to said flushed data frames (Al) when said time out period for said flushed data frame has elapsed.

23. The arrangement as claimed in one of claims 17-21, c h a r a c t e r i s e d in that said arrangement comprises means for transmitting negative acknowledgements (703) for data frames (Al) detected in advance to be timed out.

24. The arrangement as claimed in claim 23, c h a r a c t e r i s e d in that said arrangement comprises means for re-submitting data (709) frames identical to said flushed data frames (Al) if negative acknowledgements are received due to data frames (Al) detected in advance to be timed out.

25. The arrangement as claimed in one of claims 17-24, c h a r a c t e r i s e d in that said arrangement comprises means for estimating radio resources (701) to be allocated for said transmission.

26. A base station system in a packet data radio system for processing data frames (Lf, Al, B1-B2), c h a r a c t e r i s e d in that said base station system (BSS) includes an arrangement according to one of claims 17-25.

27. The base station system as claimed in claim 26, c h a r a c t e r i s e d in that said base station system (BSS) comprises means for receiving information from radio units (RU1- RU3) regarding the length and time out periods of data frames (Lf, Al, B1-B2) to be transmitted from said radio units (RU1- RU3) .

28. The base station system as claimed in claim 26 or 27, 30 c h a r a c t e r i s e d in that said base station system (BSS) comprises means for transmitting (706) instructions regarding scheduling of said data frames (Lf, Al, B1-B2) to said radio units (RU1-RU3) .

29. A radio unit for processing data frames (Lf, Al, B1-B2) in a packet data radio system, c h a r a c t e r i s e d in that said radio unit (RU1-RU3) includes an arrangement according to one of claims 17-25.

30. The radio unit as claimed in claim 29, c h a r a c t e r i s e d in that said radio unit (RU1-RU3) comprises means for transmitting (706) information to a base station system (BSS) regarding time out periods and the length of data frames (Lf, Al, B1-B2) in said radio unit (RU1-RU3) .

31. The radio unit as claimed in claim 29 or 30, c h a r a c t e r i s e d in that said radio unit (RU1-RU3) comprises means for receiving instructions from said base station system (BSS) regarding scheduling of data frames (Lf, Al, B1-B2) to be transmitted to said base station system (BSS).