(12) United States Patent
`US 6,850,540 B1
`Peisa et al.
`(45) Date of Patent:
`Feb. 1, 2005
`
`(10) Patent N0.:
`
`US006850540B1
`
`(54) PACKET SCHEDULING IN A
`COMMUNICATIONS SYSTEM
`
`(75)
`
`Inventors: Janne Johannes Peisa, Helsinki (FI);
`T00mas Wigell, Espoo (FI); Reijo
`Matinmikko, Espoo (FI); Carl Goran
`Schultz, Pargas (Fl)
`
`(73) Assignee: Telefonaktiebolaget LM Ericsson
`(publ), Stockholm (SE)
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 677 days.
`
`8/2002 Kamiya ...................... 370/468
`6,438,138 B1 *
`9/2002 Duffield et al.
`370/415
`6,452,933 B1 *
`
`........................ 709/226
`6,647,419 B1 * 11/2003 Mogul
`FOREIGN PATENT DOCUMENTS
`
`EP
`EP
`
`0859492 A2
`1030484 A2
`
`2/1998
`1/2000
`
`OTHER PUBLICATIONS
`
`Abhay K. Parekh; A Generalized Processor Sharing
`Approach to Flow Control in Integrated Services Networks:
`The Single—Node Case; IEEE; Jun. 1993; vol. 1, No. 3; pp.
`344—357.
`
`PCT International Search Report dated Jul. 12, 2001.
`
`(21) Appl. No.: 09/698,785
`
`(22)
`
`Filed:
`
`Oct. 27, 2000
`
`(60)
`
`Related US. Application Data
`Provisional application No. 60/185,005, filed on Feb. 25,
`2000, provisional application No. 60/185,003, filed on Feb.
`25, 2000, and provisional application No. 60/184,975, filed
`on Feb. 25, 2000.
`
`(30)
`
`Foreign Application Priority Data
`
`Nov. 28, 1999
`
`(GB) ............................................. 9925376
`
`Int. C1.7 ............................... H04J 3/16; H04] 3/22
`(51)
`(52) US. Cl.
`..................................... 370/468; 370/395.4
`(58) Field of Search ................................. 370/468, 230,
`370/235, 412, 395.4—395.43
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`370/348
`6/1999 Tiedemann, Jr. et al.
`5,914,950 A
`8/2000 Edwards et al.
`......... 455/4521
`6,108,552 A *
`9/2001 Wicklund ............ 370/392
`6,295,295 B1 *
`
`..... 370/232
`6,317,416 B1 * 11/2001 Giroux et al.
`
`
`6,320,845 B1 * 11/2001 DaVie ..................... 370/230
`........ 455/4522
`6,374,112 B1 *
`4/2002 Widegren et al.
`6,438,134 B1 *
`8/2002 Chow et al.
`................ 370/412
`
`m
`
`* cited by examiner
`
`Primary Examiner—Ajit Patel
`Assistant Examiner—Chirag Shah
`
`(57)
`
`ABSTRACT
`
`Methods, systems, and arrangements enable packet sched-
`uling in accordance with quality of service (QoS) constraints
`for data flows. In a Universal Mobile Telecommunications
`
`for example, a
`System (UMTS) network environment,
`Medium Access Control (MAC) layer schedules packet
`transmission of various data flows to meet stipulated criteria,
`including permitted transport format combinations (TFCs)
`from a TFC set (TFCS). In first embodiment(s), the TFC is
`selected based on guaranteed rate transmission rates,
`weighted fair queuing (WFQ) transmission rates, QoS class,
`transport block set size (TBSS), and optionally queue fill
`levels. These first embodiment(s) also further refine the
`selection process using backlog memories corresponding to
`previously unmet guaranteed and/or fair transmission rates.
`In second embodiment(s), memory requirements are
`reduced by selecting a TFC based on guaranteed rate trans-
`mission rates, QoS class, TBSS, and queue fill
`levels,
`without accommodating backlogs.
`
`39 Claims, 6 Drawing Sheets
`
`
`Receive Input iiwvs a!
`RLCs and butler dala
`
`
`
`
`Pm inlonnalion on buffer
`
`
`fll ievds in MAC entity
`
`
`Comma inlr MAC bandwidth
`share in!anon lnwlllow
`
`
`Adlusi each mpuled fair
`sham by adding me mntenis
`
`01associated backlog counter
`
`
`
`
`SelectTFC 00m TFC Sui
`
`which mmclosely mm;
`m adjuslad fairsham
`
`InsimctRLC to deliver
`
`
`packetson MAC entity
`awarding lodmsan TFC
`
`
`
`Sammie packets In MAC
`entity in amurdamo
`with ma WW TFC
`
`
`Transport tram: channels
`an physical channel
`
`
`
`Update hacking wunlers
`
`
`
`
`
`
`
`450
`
`BLACKBERRY 1013
`
`BLACKBERRY 1013
`
`

`

`US. Patent
`
`Feb. 1, 2005
`
`Sheet 1 0f 6
`
`US 6,850,540 B1
`
`130
`
`2.0fl
`
`DTCH DCCH CCCH BCCH CTCH
`
`CTCH BCCH CCCH DCCH DTCH
`
` lub
`
`CRNCISRNC
`
`110
`
`50
`
`140
`
`2
`
`

`

`nu
`
`tnetaP
`
`S”an
`
`5:55.352.29:
`
`mmm
`
`
`
`9:535953.0
`
`.I...
`
`oo.2oo
`
`5
`
`S
`
`6M2
`
`1B
`
`mRE
`
`mSEN.—
`
`Mcan
`
`S:82»:Ucan
`5,5wman“a£2520
`
`052R...
`
`«3520
`
`.853
`
`mg
`
`b.
`
`1,
`
`Mms
`
`n.—
`
`
`
`
` 01m
`
`lonuoo
`
`3
`
`

`

`US. Patent
`
`Feb. 1, 2005
`
`Sheet 3 0f 6
`
`US 6,850,540 B1
`
`400
`
`405
`
`Receive input flows at
`RLCs and butter data
`
`410
`
`Pass information on buffer
`
`fill levels to MAC entity
`
`415
`
`Compute fair MAC bandwidth
`share for each input flow
`
`420
`
`Adjust each computed fair
`
`share by adding the contents
`of associated backlog counter
`
`
`Select TFC from TFC Set
`
`
`which most closely matches
`the adjusted fair shares
`
`
`
`
`
`
`
`
`
`
`
`
`Instruct RLC to deliver
`
`packets to MAC entity
`according to chosen TFC
`
`435
`
`
`
`
`
`
`Schedule packets in MAC
`entity in accordance
`with the selected TFC
`
`
`
`Transport traffic channels
`on physical channel
`
`
`
`
`
`
`450
`Fig.4
`
`445
`
`Update backlog counters
`
`4
`
`

`

`US. Patent
`
`Feb. 1, 2005
`
`Sheet 4 0f 6
`
`US 6,850,540 B1
`
`To common RLC entities
`
`To MAC-d entities
`
`
`
`MAC—c scheduler
`5.0.5
`
`Common Transport
`Channels (RACHIFACH)
`
`510 510
`
`P185
`
`
`
`Update memories
`
`610
`
`
`
`Calculate:
`
`' Guaranteed rate transmission rates
`
`
`. WFQ transmission rates
`
`
`Add any backlog to relevant flows
`
`
`Choose TFCl for this transmission
`interval by scoring each TFC by
`1. C103 Class'min(guaranteed rate.
`T883)
`2. 008 Class’min(WFQ. T888)
`3. 003 Class‘mintQueue fill, TBSS)
`
`
`
`
`
`
`
`
`
`
`
`
`
`Fig.6
`
`
`
`
`
`Allocate chosen TBSS to flows multi-
`plexed to given transport channel by
`1. Giving all flows their guaranteed rate
`in 003 order
`2. Giving all flows their WFQ rate in 008 order
`3. Sending all packets from flows in 008 order
`
`
`
`
`
`
`
`
`
`
`
`
`
`Update backlogs for flows that still
`have data to send and did not
`get their guaranteed or WFQ rate
`
`
`
`
`
`
`5
`
`

`

`US. Patent
`
`1,w.
`
`6M5whS
`
`US 6,850,540 B1
`
`FNu.mamm£5580%.
`
`$8228m$32gnaw.xxm2m3
`emuSKaw
`
`
`MSo:oEmc.
`m.can
`
`
`
`mm:.050mg
`
`zoozoozoo10$.
`
`can
`
`man
`
`6
`
`
`

`

`US. Patent
`
`Feb. 1, 2005
`
`Sheet 6 0f 6
`
`US 6,850,540 B1
`
`M
`
`Obtain parameters for each logical channel:
`- 003 Class
`
`- Guaranteed Rate
`
`
`
`- Queue Fill Level
`
` For each logical channel. for each TFC.
`
`
`
`
`
`
`calculate two scores:
`1. Logical Channel Score=QoS Class"
`min(guaranteed rate. queue fill. T888)
`2. Logical Channel Bonus Score
`
`
`
`815
`
`
`For each TFC, calculate two scores:
`
`1. Score
`
`2. Bonus Score
`
`
`
`Select TFC based on
`
`Score and Bonus Scord
`
`Fig.8
`
`7
`
`

`

`US 6,850,540 B1
`
`1
`PACKET SCHEDULING IN A
`COMMUNICATIONS SYSTEM
`
`CROSS-REFERENCES TO RELATED
`APPLICATIONS
`
`This Non-provisional Application for Patent claims the
`benefit of priority from, and hereby incorporates by refer-
`ence the entire disclosure of, co-pending US. Provisional
`Application for Patent Ser. No. 60/185,005, filed Feb. 25,
`2000. US. Provisional Applications for Patent Ser. Nos.
`60/184,975 and 60/185,003, both filed on Feb. 25, 2000, are
`also hereby incorporated by reference in their entirety
`herein. This Non-provisional Application for Patent also
`claims the benefit of priority from Great Britain Patent
`Application No. GB9925376.7, filed in the United Kingdom
`on Oct. 28, 1999, with an inventorship of Janne Peisa.
`This Non-provisional Application for Patent is related by
`subject matter to US. Non-provisional applications for
`patent Ser. Nos. 09/698,786 and 09/698,672, both of which
`are filed on even date herewith. These two US. Non-
`
`provisional applications for patent are also hereby incorpo-
`rated by reference in their entirety herein.
`
`BACKGROUND OF THE INVENTION
`
`1. Technical Field of the Invention
`
`The present invention relates in general to the field of
`communications systems, and in particular, by way of
`example but not limitation, to scheduling packets of data/
`informational flows having differing priority levels in a
`communications system.
`2. Description of Related Art
`Access to and use of wireless networks is becoming
`increasingly important and popular for business, social, and
`recreational purposes. Users of wireless networks now rely
`on them for both voice and data communications.
`
`Furthermore, an ever increasing number of users demand
`both an increasing array of services and capabilities as well
`as greater bandwidth for activities such as Internet surfing.
`To address and meet the demands for new services and
`
`the wireless communications industry
`greater bandwidth,
`constantly strives to improve the number of services and the
`throughput of their wireless networks. Expanding and
`improving the infrastructure necessary to provide additional
`services and higher bandwidth is an expensive and
`manpower-intensive undertaking. Moreover, high-
`bandwidth data streams will eventually be demanded by
`consumers to support features such as real-time audio-visual
`downloads and live audio-visual communication between
`
`two or more people. In the future, it will therefore become
`necessary and/or more cost-effective to introduce next gen-
`eration wireless system(s) instead of attempting to upgrade
`existing system(s).
`To that end, the wireless communications industry intends
`to continue to improve the capabilities of the technology
`upon which it relies and that
`it makes available to its
`customers by deploying next generation system(s). Proto-
`cols for a next-generation standard that is designed to meet
`the developing needs of wireless customers is being stan-
`dardized by the 3rd Generation Partnership Project (3GPP).
`The set of protocols is known collectively as the Universal
`Mobile Telecommunications System (UMTS).
`Referring now to FIG. 1, an exemplary wireless commu-
`nications system with which the present invention may be
`advantageously employed is illustrated generally at.100. In
`a UMTS network 100,
`the network 100 includes a core
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`network 120 and a UMTS Terrestrial Radio Access Network
`
`(UTRAN) 130. The UTRAN 130 is composed of, at least
`partially, a number of Radio Network Controllers (RNCs)
`140, each of which may be coupled to one or more neigh-
`boring Node Bs 150. Each Node B 150 is responsible for a
`given geographical cell. and the controlling RNC 140 is
`responsible for routing user and signaling data between that
`Node B 150 and the core network 120. All of the RNCs 140
`may be directly or indirectly coupled to one another. A
`general outline of the UTRAN 130 is given in Technical
`Specification TS 25.401 V2.0.0 (1999-09) of the 3rd Gen-
`eration Partnership Project, 3GPP, which is hereby incorpo-
`rated by reference in its entirety herein. The UMTS net-
`work.100 also includes multiple user equipments (UEs) 110.
`UE may include, for example, mobile stations, mobile
`terminals, laptops/personal digital assistants (PDAs) with
`wireless links, etc.
`In conventional wireless systems, data transmissions and/
`or access requests compete for bandwidth based on first
`come, first served and/or random paradigms. Each mobile
`station, and its associated transmissions, typically acquire
`access to a network using some type of request (e.g., a
`message) prior to establishing a connection. Once the
`mobile station has established a connection,
`the mobile
`station receives a predetermined transmission bandwidth
`that is usually mandated by the air interface requirements of
`the relevant system. In a UMTS network, on the other hand,
`transmission bandwidth is variable, more flexible, and some-
`what separated from the physical channel maximum man-
`dated by-the air interface requirements of UMTS. However,
`certain guaranteed bandwidth and/or quality of service (Qos)
`requirements must be provided to the UEs. There is there-
`fore a need to ensure that the guaranteed bandwidth and/or
`QoS is provided to each respective UE in the variable and
`flexible environment of UMTS.
`
`SUMMARY OF THE INVENTION
`
`The above-identified deficiencies, as well as others, that
`are associated with existing schemes are remedied by the
`methods, systems, and arrangements of the present inven-
`tion. For example, as heretofore unrecognized, it would be
`beneficial to be able to handle specified guaranteed band-
`width and QoS requirements when multiplexing more than
`one incoming data flow onto a single output channel. In fact,
`it would be beneficial if a two-level scheduling mechanism
`was employed in order to maintain guaranteed bit rates to the
`extent practicable as queued input flows are multiplexed
`onto a single output flow.
`Methods, systems, and arrangements in accordance with
`certain embodiment(s) of the present
`invention enable
`packet scheduling in accordance with quality of service
`(QoS) constraints for data flows in communications systems.
`In a Universal Mobile Telecommunications System (UMTS)
`network environment, for example, a Medium Access Con-
`trol (MAC) layer schedules packet transmission of various
`data flows to meet stipulated criteria, including permitted
`transport format combinations (TFCs)
`from a TFC set
`(TFCS). In first embodiment(s), the TFC is selected based on
`guaranteed rate transmission rates, weighted fair queuing
`(WFQ) transmission rates, QoS class, transport block set
`size (TBSS), and optionally queue fill levels. These first
`embodiment(s) also further refine the selection process using
`backlog memories corresponding to previously unmet guar-
`anteed and/or fair transmission rates. In second embodiment
`(s), memory requirements are reduced by selecting a TFC
`based on guaranteed rate transmission rates, QoS class,
`TBSS, and queue fill levels, without accommodating back-
`logs corresponding to previously unsatisfied requirements.
`
`8
`
`

`

`3
`
`4
`
`US 6,850,540 B1
`
`In certain first embodiment(s), a scheduling method for
`providing bandwidth to entities in a communications system
`includes the steps of: calculating a first transfer rate for
`multiple flows; calculating a second transfer rate for the
`multiple flows; ascertaining a quality of service (QoS) for
`each flow of the multiple flows; and assigning bandwidth to
`each flow of the multiple flows responsive to the first
`transfer rate, the second transfer rate, and the QoS for each
`flow of the multiple flows. In a preferred embodiment, the
`first
`transfer rate may correspond to a guaranteed rate
`transfer rate, and the second transfer rate may correspond to
`a weighted fair queuing (WFQ) transfer rate. In another
`preferred embodiment, the first and second transfer rates
`may correspond to aggregated transfer rates over the mul-
`tiple flows.
`In certain second embodiment(s), a scheduling method for
`providing bandwidth to entities in a communications system
`includes the steps of: ascertaining a quality of service (QoS)
`class that is associated with each channel of multiple chan-
`nels; ascertaining a guaranteed rate transmission rate for
`each channel; ascertaining a queue fill level of a queue that
`corresponds to each channel; calculating a first score for
`each channel responsive to the QoS class, the guaranteed
`rate transmission rate, and the queue fill level. In a preferred
`embodiment, an additional step of calculating a second score
`for each channel responsive to the guaranteed rate transmis-
`sion rate and the queue fill level is included.
`The above-described and other features of the present
`invention are explained in detail hereinafter with reference
`to the illustrative examples shown in the accompanying
`drawings. Those skilled in the art will appreciate that the
`described embodiments are provided for purposes of illus-
`tration and understanding and that numerous equivalent
`embodiments are contemplated herein.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`Amore complete understanding of the methods, systems,
`and arrangements of the present invention may be had by
`reference to the following detailed description when taken in
`conjunction with the accompanying drawings wherein:
`FIG. 1 illustrates an exemplary wireless communications
`system with which the present invention may be advanta-
`geously employed;
`FIG. 2 illustrates a protocol model for an exemplary
`next-generation system with which the present invention
`may be advantageously employed;
`FIG. 3 illustrates a view of an exemplary second layer
`architecture of an exemplary next-generation system in
`accordance with the present invention;
`FIG. 4 illustrates an exemplary method in flowchart form
`for allocating bandwidth resources to data flow streams
`between entities in the exemplary second layer architecture
`of FIG. 3;
`FIG. 5 illustrates an exemplary environment for schedul-
`ing data flows in accordance with the present invention;
`FIG. 6 illustrates an exemplary method in flowchart form
`for scheduling data flows in accordance with the present
`invention;
`FIG. 7 illustrates another view of the exemplary second
`layer architecture of an exemplary next-generation system in
`accordance with the present invention; and
`FIG. 8 illustrates another exemplary method in flowchart
`form for scheduling data flows in accordance with the
`present invention.
`DETAILED DESCRIPTION OF THE DRAWINGS
`
`In the following description, for purposes of explanation
`and not limitation, specific details are set forth, such as
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`for
`logic modules (implemented in,
`particular circuits,
`example, software, hardware, firmware, some combination
`thereof, etc.), techniques, etc. in order to provide a thorough
`understanding of the invention. However, it will be apparent
`to one of ordinary skill in the art that the present invention
`may be practiced in other embodiments that depart from
`these specific details. In other instances, detailed descrip-
`tions of well-known methods, devices, logical code (e.g.,
`hardware, software, firmware, etc.), etc. are omitted so as
`not to obscure the description of the present invention with
`unnecessary detail.
`A preferred embodiment of the present invention and its
`advantages are best understood by referring to FIGS. 1—8 of
`the drawings, like numerals being used for like and corre-
`sponding parts of the various drawings. Aspects of the
`UMTS are used to describe a preferred embodiment of the
`present invention. However, it should be understood that the
`principles of the present invention are applicable to other
`wireless communication standards (or systems), especially
`those in which communication is packet-based.
`Referring now to FIG. 2, a protocol model for an exem-
`plary next-generation system with which the present inven-
`tion may be advantageously employed is illustrated gener-
`ally at 200. In the protocol model 200 (e.g., for a Forward
`Access CHannel (FACH) transport channel type), the “UU”
`indicates the interface between UTRAN 130 and the UE
`110, and “Iub” indicates the interface between the RNC 140
`and a Node B 150 (where “Node B” is a generalization of,
`for example, a Base Transceiver Station (BTS)). User and
`signaling data may be carried between an RNC 140 and a
`UE 110 using Radio Access Bearers (RABs) (as illustrated
`hereinbelow with reference to FIG. 3). Typically, a UE 110
`is allocated one or more RABs, each of which is capable of
`carrying a flow of user or signaling data. RABs are mapped
`onto respective logical channels. At the Media Access Con-
`trol (MAC) layer, a set of logical channels is mapped in turn
`onto a transport channel, of which there are two types: a
`“common” transport channel which is shared by different
`UEs 110 and a “dedicated” transport channel which is
`allocated to a single UE 110 (thus leading to the terms
`“MAC-c” and “MAC-d”). One type of common channel is
`the FACH. A basic characteristic of a FACH is that it is
`
`possible to send one or more fixed size packets per trans-
`mission time interval (e.g., 10, 20, 40, or 80 ms). Several
`transport channels (e.g., FACHs) are in turn mapped at the
`physical layer onto a Secondary Common Control Physical
`CHannel (S-CCPCH) for transmission over the air interface
`between a Node B 150 and a UE 110.
`
`When a UE 110 registers with an RNC 140 via a Node B
`150, that RNC 140 acts at least initially as both the serving
`and the controlling RNC 140 for the UE 110. (The serving
`RNC 140 may subsequently differ from the controlling RNC
`140 in a UMTS network 100, but the presence or absence of
`this condition is not particularly relevant here.) The RNC
`140 both controls the air interface radio resources and
`
`terminates the layer 3 intelligence (e.g., the Radio Resource
`Control (RRC) protocol). thus routing data associated with
`the UE 110 directly to and from the core network 120.
`It should be understood that the MAC-c entity in the RNC
`140 transfers MAC-c Packet Data Units (PDUs) to the peer
`MAC-c entity at the UE 110 using the services of the FACH
`Frame Protocol (FACH FP) entity between the RNC 140 and
`the Node B 150. The FACH FP entity adds header infor-
`mation to the MAC-c PDUs to form FACH FP PDUs which
`
`are transported to the Node B 150 over an AAL2 (or other
`transport mechanism) connection. An interworking function
`at the Node B 150 interworks the FACH frame received by
`the FACH FP entity into the PHY entity.
`
`9
`
`

`

`US 6,850,540 B1
`
`5
`In an exemplary aspect of the scenario illustrated in FIG.
`2, an important task of the MAC-c entity is the scheduling
`of packets (MAC PDUs) for transmission over the air
`interface. If it were the case that all packets received by the
`MAC-c entity were of equal priority (and of the same. size),
`then scheduling would be a simple matter of queuing the
`received packets and sending them on a first come first
`served basis (e.g.,
`first-in,
`first-out (FIFO)). However,
`UMTS defines a framework in which different Quality of
`Services (QoSs) may be assigned to different RABs. Packets
`corresponding to a RAB that has been allocated a high QoS
`should be transmitted over the air interface at a high priority
`whilst packets corresponding to a RAB that has been allo-
`cated a low QoS should be transmitted over the air interface
`at a lower priority. Priorities may be determined at the MAC
`entity (e.g., MAC-c or MAC-d) on the basis of RAB
`parameters.
`UMTS deals with the question of priority by providing at
`the controlling RNC 140 a set of queues for each FACH. The
`queues may be associated with respective priority levels. An
`algorithm, which is defined for selecting packets from the
`queues in such a way that packets in the higher priority
`queues are (on average) dealt with more quickly than
`packets in the lower priority queues, is implemented. The
`nature of this algorithm is complicated by the fact that the
`FACHs that are sent on the same physical channel are not
`independent of one another. More particularly, a set of
`Transport Format Combinations (TFCs) is defined for each
`S-CCPCH, where each TFC includes a transmission time
`interval, a packet size, and a total
`transmission size
`(indicating the number of packets in the transmission) for
`each FACH. The algorithm should select for the FACHs a
`TFC which matches one of those present in the TFC set in
`accordance with UMTS protocols.
`Preferably, a packet received at the controlling RNC 140
`is placed in a queue (for transmission on a FACH), where the
`queue corresponds to the priority level attached to the packet
`as well as to the size of the packet. The FACH is mapped
`onto a S-CCPCH at a Node B 150 or other corresponding
`node of the UTRAN 130. In an alternative preference, the
`packets for transmission on the FACH are associated with
`either a Dedicated Control CHannel (DCCH) or to a Dedi-
`cated Traffic CHannel (DTCH). It should be noted that,
`preferably, each FACH is arranged to carry only one size of
`packets. However, this is not necessary, and it may be that
`the packet size that can be carried by a given FACH varies
`from one transmission time interval to another.
`
`As alluded to hereinabove, the UE 110 may communicate
`with the core network 120 of the UMTS system 100 via
`separate serving and controlling (or drift) RNCs 140 within
`the UTRAN 130 (e.g., when the UE 110 moves from an area
`covered by the original serving RNC 140 into a new area
`covered by a controlling/drift RNC 140) (not specifically
`shown). Signaling and user data packets destined for the UE
`110 are received at the MAC-d entity of the serving RNC
`140 from the core network 120 and are “mapped” onto
`logical channels, namely a Dedicated Control CHannel
`(DCCH) and a Dedicated traffic CHannel (DTCH),
`for
`example. The MAC-d entity constructs MAC Service Data
`Units (SDUS), which include a payload section containing
`logical channel data and a MAC header containing, inter
`alia, a logical channel identifier. The MAC-d entity passes
`the MAC SDUs to the FACH FP entity. This FACH FP entity
`adds a further FACH FP header to each MAC SDU, where
`the FACH FP header includes a priority level that has been
`allocated to the MAC SDU by an RRC entity. The RRC is
`notified of available priority levels, together with an iden-
`
`6
`tification of one or more accepted packet sizes for each
`priority level, following the entry of a UE 110 into the
`coverage area of the drift RNC 140.
`The FACH FP packets are sent to a peer FACH FP entity
`at the drift RNC 140 over an AAL2 (or other) connection.
`The peer FACH FP entity decapsulates the MAC-d SDU and
`identifies the priority contained in the FRAME FP header.
`The SDU and associated priority are passed to the MAC-c
`entity at the controlling RNC 140. The MAC-c layer is
`responsible for scheduling SDUs for transmission on the
`FACHs. More particularly, each SDU is placed in a queue
`corresponding to its priority and size. For example, if there
`are 16 priority levels, there will be 16 queue sets for each
`FACH, with the number of queues in each of the 16 queue
`sets depending upon the number of packet sizes accepted for
`the associated priority. As described hereinabove, SDUs are
`selected from the queues for a given FACH in accordance
`with some predefined algorithm (e.g., so as to satisfy the
`TFC requirements of the physical channel).
`The scheme described hereinbelow with reference to
`FIGS. 3 and 4 relates to data transmission in a telecommu-
`
`nications network and in particular, though not necessarily,
`to data transmission in a UMTS.
`
`the 3GPP is currently in the
`As noted hereinabove,
`process of standardizing a new set of protocols for mobile
`telecommunications systems. The set of protocols is known
`collectively as the UMTS. With reference to FIG. 3, a view
`of an exemplary second layer architecture of an exemplary
`next-generation system in accordance with the present
`invention is illustrated generally at 300. Specifically, by way
`of example only, the exemplary second layer architecture
`300 illustrates a simplified UMTS layer 2 protocol structure
`which is involved in the communication between mobile
`
`stations (e.g. mobile telephones), or more broadly UEs 110,
`and Radio Network Controllers (RNCS) 140 of a UMTS
`network 100. The RNCs 140. are analogous to the Base
`Station Controllers (BSCs) of existing GSM mobile tele-
`communications networks., communicating with the mobile
`stations via Node Bs 150.
`
`The layer 2 structure of the exemplary second layer
`architecture 300 includes a set of Radio Access Bearers
`
`(RABs) 305 that make available radio resources (and
`services) to user applications. For each mobile station there
`may be one or several RABs 305. Data flows (e.g., in the
`form of segments) from the RABs 305 are passed to respec-
`tive Radio Link Control (RLC) entities 310, which amongst
`other tasks buffer the received data segments. There is one
`RLC entity 310 for each RAB 305. In the RLC layer, RABs
`305 are mapped onto respective logical channels 315. A
`Medium Access Control (MAC) entity 320 receives data
`transmitted in the logical channels 315 and further maps the
`data from the logical channels 315 onto a set of transport
`channels 325. The transport channels 325 are finally mapped
`to a single physical transport channel 330, which has a total
`bandwidth (e.g., of <2Mbits/sec) allocated to it by the
`network. Depending whether a physical channel is used
`exclusively by one mobile station or is shared between many
`mobile stations,
`it
`is referred to as either a “dedicated
`physical channel” or a “common channel”. A MAC entity
`connected to a dedicated physical channel
`is known as
`MAC-d;
`there is preferably one MAC-d entity for each
`mobile station. A MAC entity connected to a common
`channel is known as MAC-c; there is preferably one MAC-c
`entity for each cell.
`The bandwidth of a transport channel 325 is not directly
`restricted by the capabilities of the physical layer 330, but is
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`10
`
`10
`
`

`

`US 6,850,540 B1
`
`7
`
`rather configured by a Radio Resource Controller (RRC)
`entity 335 using Transport Formats (TFs). For each transport
`channel 325,
`the RRC entity 335 defines one or several
`Transport Block (TB) sizes. Each Transport Block size
`directly corresponds to an allowed MAC Protocol Data Unit
`(PDU) and tells the MAC entity what packet sizes it can use
`to transmit data to the physical layer. In addition to block
`size, the RRC entity 335 informs the MAC entity 320 of a
`Transport Block Set (TBS) size, which is the total number of
`bits the MAC entity can transmit to the physical layer in a
`single transmission time interval (TTI). The TB size and
`TBS size, together with some additional information relating
`to the allowed physical layer configuration, form a TF. An
`example of a TF is (TB=80 bits, TBS=160 bits), which
`means that the MAC entity 320 can transmit two 80 bit
`packets in a single TTI. Thus, this TF can be written as
`TF=(80, 160). The RRC entity 335 also informs the MAC
`entity of all possible TFs for a given transport channel. This
`combination of TFs is called a Transport Format Combina-
`tion (TFC). An example of a TFC is {TF1=(80, 80), TF2=
`(80, 160)}. In this example, the MAC entity can choose to
`transmit one or two PDUs in one TTI on the particular
`transport channel in question; in both cases, the PDUs have
`a size of 80 bits.
`
`In each TTI, the MAC entity 320 has to decide how much
`data to transmit on each transport channel 325 connected to
`it. These transport channels 325 are not independent of one
`another, and are later multiplexed onto a single physical
`channel 330 at
`the physical
`layer 330 (as discussed
`hereinabove). The RRC entity 335 has to ensure that the total
`transmission capability on all transport channels 325 does
`not exceed the transmission capability of the underlying
`physical channel 330. This is accomplished by giving the
`MAC entity 320 a Transport Format Combination Set
`(TFCS), which contains the allowed Transport Format Com-
`binations for all transport channels.
`By way of example, consider a MAC entity 320 which has
`two transport channels 325 that are further multiplexed onto
`a single physical channel 330, which has a transport capacity
`of 160 bits per transmission time interval (It should be
`understood that,
`in practice,
`the capacity will be much
`greater than 160). The RRC entity 335 could decide to assign
`three transport formats TF1=(80, 0), TF2=(80, 80) and
`TF3=(80, 160)
`to both transport channels 325. Clearly
`however, the MAC entity 320 cannot choose to transmit on
`both transport channels 325 at the same time using TF3 as
`this would result in the need to transmit 320 bits on the
`
`physical channel 330, which has only a capability to transmit
`160 bits. The RRC entity 335 has to restrict
`the total
`transmission rate by not allowing all combinations of the
`TFs. An example of this would be a,TFCS as follows [{ (80,
`0), (80, 0)}, { (80, 0), (80, 80)}, { (80, 0), (80, 160)}, { (80,
`80), (80, 0)}, { (80, 80), (80, 80)}, { (80, 160), (80, 0)}],
`where the transport format of transport channel “1” is given
`as the first element of each element pair, and the transport
`format of transport channel “2” is given as the second
`element. As the MAC entity 320 can only choose one of
`these allowed transport format combinations from the trans-
`port format combination set, it is not possible to exceed the
`capability of the physical channel 330.
`An element of the TFCS is pointed out by a Transport
`Format Combination Indicator (TFCI), which is the index of
`the corresponding TFC. For example,
`in the previous
`example there are 6 different TFCs., meaning that the TFCI
`can take any value between 1 and 6. The TFCI=2 would
`correspond to the second TFC, which is { (80, 0), (80, 80)},
`meaning that nothing is transmitted from the first transport
`
`8
`channel and a single packet of 80 bits is transmitted from the
`second transport channel.
`It
`is of course necessary to share the total available
`bandwidth between the logical channels 315. The decision to
`distribute the bandwidth to different transport channels is
`made by the MAC entity 320 for each transmission time
`interval by choosing a suitable TFCI. This sharing of band-
`width can be done in several ways, for example by giving an
`absolute preference to flows which are considered to be
`more important
`than others. This would be the easiest
`method to implement, but can result in a very unfair distri