Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-03-19
2001-05-22
Chin, Wellington (Department: 2735)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S416000, C455S452200
Reexamination Certificate
active
06236656
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field of the Invention
The present invention relates in general to the radio communications field and, in particular, to a system and method for scheduling data transfers in wireless data communications systems.
2. Description of Related Art
In the new generation of wireless data communication services, such as, for example, the General Packet Radio Service (GPRS) in the Global System for Mobile Communications (GSM), data packets are transferred from one application to another across a radio air interface. As such, the GPRS provides a means for transporting an application from a host transmitter to a receiver. In that regard, data packets (typically Internet Protocol or IP packets) are submitted to a GPRS at one access point, transported through the GPRS system, and ultimately delivered at a second GPRS access point.
In the GPRS Service Description, Stage 1 (Technical Specification GSM 02.60, version 5.1.0), a number of different Quality of Service (QoS) classes are described. Each such QoS class is further described by a set of service parameters. These QoS parameters include maximum delay, minimum mean throughput, priority, and level of reliability. Each service session (e.g., “Packet Data Processing or PDP context” in GPRS) subscribes to one QoS class. The end-to-end performance of the GPRS is of importance to an application. Consequently, all QoS parameters are defined from access point to access point.
As such, in accordance with the GPRS specification, QoS in a GPRS is measured between either the “R” or “S” and the “Gi” reference points. A GPRS is required to provide each service session with a bearer service that conforms to the QoS class agreed upon. Generally, this means scheduling the transmission of incoming data packets. Given a set of data packets with different QoS requirements, and different arrival times with respect to the GPRS system, a significant problem is to determine in what order these packets should be transmitted over different links in order to comply with the promised QoS requirements of the respective QoS classes. This scheduling problem is complicated by the fact that the throughput per link depends on the radio link conditions. Consequently, the throughput per radio link differs from user to user, and from one instant of time to another. This fact also implies that the total bandwidth on a link or in a cell depends on the user of the link, and therefore, on the scheduling of the packet transmissions.
Furthermore, a GPRS is divided into different subsystems, which adds to the complexity of the scheduling problem. Note, as mentioned earlier, that the QoS is measured end-to-end in a GPRS system, in addition to, for example, the QoS delay, and the sum of the delays in the Switching System (SS) part and Base Station System (BSS) part of the data communications system. More precisely, the QoS delay time is the sum of the queuing times in the Gateway GPRS Support Node (GGSN), Serving GPRS Support Node (SGSN), Packet Control Unit (PCU), the processing time, and the transmission time over all of the links. However, in a properly dimensioned GPRS system, the largest contributors to the overall delay are the queuing times and the transmission time over the radio air interface.
Existing algorithms place some scheduling functions in the SS part of the system (more specifically, in the Logical Link Control or LLC protocol layer), and some others in the BSS part (in the MAC/RLC protocol layer). The scheduling function in the SS concerns the order in which to submit LLC frames to the BSS. The SS scheduling function is accomplished by considering the data packet arrival times and the QoS parameters of the corresponding data flow. In addition, the SS scheduling function can consider some limited information about the data queues in the BSS, and estimated total bandwidth in each cell.
The scheduling function in the BSS determines in which order, and on which radio links, to transmit arriving LLC frames. In the BSS′ scheduling function, the BSS can consider whatever information it has about the quality of the radio links, and the time at which the LLC frame was submitted to the BSS from the SS. In addition, the BSS can consider some very limited information about the relative importance of the LLC frames, which can be provided by the SS. For example, in the solutions for QoS and flow control presented in the GSM Technical Specifications 02.60 and 08.18 (BSS-SGSN; BSS GPRS Protocol, version 5.0.0), the SS information about the BSS′ conditions is limited to the estimated total average bandwidth in each cell and restricted information about the length of the BSS queues, as carried in flow control messages.
The existing systems and scheduling techniques are incapable of implementing a workable QoS solution for a GPRS. In addition, the existing systems and scheduling techniques suffer from fundamental flaws, which can lead to excessive processor load, bad link-utilization, and poor throughput. The following examples illustrate these problems.
One problem is that the existing systems and scheduling techniques are unable to determine how well the QoS requirements imposed by subscribers are satisfied. Specifically, the BSS part of the system does not know the queuing time in the SS part. Consequently, the BSS is unable to determine the end-to-end delay. On the other hand, in at least the LLC “unacknowledge” mode of operation, the SS does not know the exact moment at which an LLC frame is transmitted over the radio air interface. Consequently, the SS is unable to determine the end-to-end delay. There is no information provided in a GPRS system about the end-to-end delay. Consequently, it is not possible to determine whether the GPRS bearer service meets the agreed upon delay requirements.
Another problem is that the existing systems and scheduling techniques are unable to control end-to-end delay times through a GPRS system. Specifically, the SS does not know the individual users' radio link conditions. As such, even if the SS had information about the lengths of the queues in the BSS, the SS still would not know how much time it would take to empty the BSS′ queues. This problem occurs because the time it takes to transmit packets from the queues depends on the radio link conditions for each user having packets in the queues.
Furthermore, the SS typically does not know enough details about how the BSS′ scheduling is accomplished. Consequently, the SS is unable to determine the amount of time a submitted LLC frame will spend in the BSS′ queues before it is transmitted over the radio air interface. Therefore, similar to the BSS case, the SS is unable to control the GPRS′ end-to-end packet delay.
Still another problem is that the existing systems and scheduling techniques are unable to deal with questions concerning the trade-offs between maximum bandwidth utilization and priority of users. Specifically, consider the situation wherein certain users having a high priority are suffering with poor radio link conditions, while other users having a low priority are enjoying high throughput per radio link. The system has to deal with the delicate task of choosing between the high throughput (low priority users) or providing resources to the high priority users. On the one hand, by providing all resources to the low priority, high link-throughput users, the system's overall throughput will be maximized. On the other hand, by providing all resources to the high priority users, the system will ensure that these users' high priority requirements are indeed realized. However, this prioritizing will be realized with the expense of poor throughput in the system. As such, situations such as these can be expected to occur frequently in any packet data radio system.
In existing data communications systems, the BSS knows too little about the QoS requirements to make appropriate scheduling decisions in the above-described situations. In contrast, the SS knows little or nothing about the throughput per us
Forslöw Jan
Westerberg Erik
Chin Wellington
Jenkens & Gilchrist
Jones Prenell
Telefonaktiebolaget LM Ericsson (publ)
LandOfFree
Link-efficiency based scheduling in radio data... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Link-efficiency based scheduling in radio data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Link-efficiency based scheduling in radio data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2494866