`Peisa et al.
`
`I lllll llllllll Ill lllll lllll lllll lllll lllll 111111111111111111111111111111111
`US006850540B 1
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 6,850,540 Bl
`Feb.1,2005
`
`(54) PACKET SCHEDULING IN A
`COMMUNICATIONS SYSTEM
`
`(75)
`
`Inventors: Janne Johannes Peisa, Helsinki (FI);
`Toomas Wigell, Espoo (FI); Reijo
`Matinmikko, Espoo (FI); Carl Goran
`Schultz, Pargas (FI)
`
`(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.
`
`(21) Appl. No.: 09/698,785
`
`(22) Filed:
`
`Oct. 27, 2000
`
`Related U.S. Application Data
`( 60) 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.
`Foreign Application Priority Data
`
`(30)
`
`Nov. 28, 1999
`
`(GB) ............................................. 9925376
`
`Int. Cl.7 ............................... H04J 3/16; H04J 3/22
`(51)
`(52) U.S. 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
`
`5,914,950 A
`6,108,552 A *
`6,295,295 Bl *
`6,317,416 Bl *
`6,320,845 Bl *
`6,374,112 Bl *
`6,438,134 Bl *
`
`6/1999
`8/2000
`9/2001
`11/2001
`11/2001
`4/2002
`8/2002
`
`Tiedemann, Jr. et al. ... 370/348
`Edwards et al. ......... 455/452.1
`Wicklund ................... 370/392
`Giroux et al.
`.............. 370/232
`Davie ......................... 370/230
`Widegren et al. ........ 455/452.2
`Chow et al. ................ 370/412
`
`6,438,138 Bl * 8/2002 Kamiya ...................... 370/468
`6,452,933 Bl * 9/2002 Duffield et al. ............. 370/415
`6,647,419 Bl * 11/2003 Mogul ........................ 709/226
`
`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.
`* cited by examiner
`
`Primary Examiner-Ajit Patel
`Assistant Examiner---Chirag Shah
`
`(57)
`
`ABSTRACT
`
`Methods, systems, and arrangements enable packet sched(cid:173)
`uling in accordance with quality of service (QoS) constraints
`for data flows. In a Universal Mobile Telecommunications
`System (UMTS) network environment, for example, a
`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 (TESS), 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(cid:173)
`mission rates, QoS class, TESS, and queue fill levels,
`without accommodating backlogs.
`
`39 Claims, 6 Drawing Sheets
`
`Page 1 of 20
`
`
`
`U.S. Patent
`
`Feb.1,2005
`
`Sheet 1 of 6
`
`US 6,850,540 Bl
`
`140
`
`130
`
`120
`
`Fig.1
`
`DTCH DCCH CCCH BCCH CTCH
`
`CTCH BCCH CCCH DCCH OTCH
`
`MAC-c
`
`PHY
`
`UE
`
`110
`
`PHY
`
`AAL2
`
`ATM
`
`Uu
`
`NodeB
`Fig.2
`
`lub
`
`150
`
`MAC-c
`FachFP
`AAL2
`
`ATM
`CRNC/SRNC
`
`140
`
`Page 2 of 20
`
`
`
`lo-"
`~
`Q
`.i;;..
`'&.
`Q
`(It
`~
`-..a-..
`rJ'J.
`e
`
`O'I
`0 .....,
`N
`~ .....
`'Jl =-~
`
`N c c
`!""
`"?'
`~
`"'!"j
`
`Ul
`
`~ = ......
`~ ......
`~
`•
`\JJ.
`d •
`
`330
`
`L1
`
`I
`
`320
`
`LL2/MAC
`
`325
`Channels
`Transport
`
`PHY
`
`MAC
`
`Channels
`Logical
`
`315
`
`L2/RLC
`
`I
`
`I I "" I 3iO
`
`310
`
`I RLC I 1
`
`310
`
`3101
`
`Fig.3
`
`I
`Q Q Q ~ 305
`
`I
`
`I
`
`I
`
`I 310
`
`I
`
`I I Cl I"'
`
`310 I
`
`II
`
`8
`c:
`....
`0
`
`..... - c::
`
`8
`e
`
`ail!!
`
`U·plane information
`
`Page 3 of 20
`
`
`
`U.S. Patent
`
`Feb. 1,2005
`
`Sheet 3 of 6
`
`US 6,850,540 Bl
`
`405
`Receive input flows at
`RLCs and buffer 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
`425
`Select TFC from TFC Set
`which most closely matches
`the adjusted fair shares
`430
`Instruct RLC to deliver
`packets to MAC entity
`according to chosen TFC
`435
`Schedule packets in MAC
`entity in accordance
`with the selected TFC
`440
`
`Transport traffic channels
`on physical channel
`
`445
`Update backlog counters
`
`450
`
`Fig.4
`
`Page 4 of 20
`
`
`
`U.S. Patent
`
`Feb.1,2005
`
`Sheet 4 of 6
`
`US 6,850,540 Bl
`
`To common RLC entities
`
`To MAC-d entities
`
`MAC-c scheduler
`~
`
`QoS Buffers
`
`Fig.5
`
`Common Transport
`Channels {RACH/FACH)
`
`510 510
`
`• ,r-605
`I Update memories I
`~
`
`,..--610
`
`Calculate:
`• Guaranteed rate transmission rates
`• WFQ transmission rates
`Add any backlog to relevant flows
`
`•
`
`Allocate chosen TBSS to flows multi-
`plexed to given transport channel by
`1. Giving all flows their guaranteed rate
`in QoS order
`2. Giving all flows their WFQ rate in QoS order
`3. Sending all packets from flows in QoS order
`+
`,..--625
`Update backlogs for flows that still
`have data to send and did not
`get their guaranteed or WFQ rate
`I
`
`•
`
`Choose TFCI for this transmission
`interval by scoring each TFC by
`1. QoS Class*min(guaranteed rate,
`TBSS)
`2. QoS Class*min(WFQ, TBSS)
`3. QoS Class*min(Queue fill, TBSS}
`
`_,.-615
`
`,r-620
`
`Fig.6
`
`Page 5 of 20
`
`
`
`lo-"
`~
`Q
`.i;;..
`'&.
`Q
`(It
`~
`-..a-..
`rJ'J.
`e
`
`O'I
`0 .....,
`Ul
`~ .....
`'Jl =(cid:173)~
`
`N c c
`'"""' ~
`?'
`~
`"'!"j
`
`Ul
`
`~ = ......
`~ ......
`~
`•
`\JJ.
`d •
`
`OCH
`
`OCH
`
`OCH
`
`Fig.7
`
`FACH
`
`725
`
`MUX
`
`Channel Switching
`
`Scheduling
`
`MAC-d
`
`--c::::==:::::::::::::::-----c::::=::::::::==========::?::---715
`
`735
`
`720
`
`MAC-c
`
`710
`
`I RLC
`
`Buffer
`POU
`RLC
`
`RLC
`
`Buffer
`POU
`RLC
`
`Radio Access
`
`Bearer#2
`
`730
`
`(
`
`Radio Access
`
`Bearer#1
`
`730
`
`(
`
`705
`
`RLC
`
`RRC
`
`710
`
`OtherUEs
`Traffic from
`
`Buffer
`POU
`RLC
`
`RLC I
`
`710-.J
`
`I
`
`RRC
`
`705
`
`Z!lil
`
`Page 6 of 20
`
`
`
`U.S. Patent
`
`Feb. 1, 2005
`
`Sheet 6 of 6
`
`US 6,850,540 Bl
`
`,--sos
`"
`Obtain parameters for each logical channel:
`•QoS Class
`• Guaranteed Rate
`• Queue Fill Level
`,,.--810
`,,
`For each logical channel, for each TFC.
`calculate two scores:
`1. Logical Channel Score=QoS Class*
`min(guaranteed rate, queue fill, TBSS)
`2. Logical Channel Bonus Score
`
`'I
`
`_,...,.---815
`
`For each TFC, calculate two scores:
`1. Score
`2. Bonus Score
`
`,--s20
`,
`Select TFC based on
`Score and Bonus Scord
`
`Fig.8
`
`Page 7 of 20
`
`
`
`US 6,850,540 Bl
`
`10
`
`15
`
`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-
`s 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(cid:173)
`rated by reference in its entirety herein. The UMTS net(cid:173)
`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
`20 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
`25 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(cid:173)
`what separated from the physical channel maximum man(cid:173)
`dated by-the air interface requirements of UMTS. However,
`30 certain guaranteed bandwidth and/or quality of service (Qos)
`requirements must be provided to the UEs. There is there(cid:173)
`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.
`
`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(cid:173)
`ence the entire disclosure of, co-pending U.S. Provisional
`Application for Patent Ser. No. 60/185,005, filed Feb. 25,
`2000. U.S. 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 U.S. 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 U.S. Non(cid:173)
`provisional applications for patent are also hereby incorpo(cid:173)
`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 35
`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
`greater bandwidth, the wireless communications industry
`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(cid:173)
`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 50
`two or more people. In the future, it will therefore become
`necessary and/or more cost-effective to introduce next gen(cid:173)
`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(cid:173)
`cols for a next-generation standard that is designed to meet
`the developing needs of wireless customers is being stan(cid:173)
`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(cid:173)
`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
`
`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-
`40 tion. For example, as heretofore unrecognized, it would be
`beneficial to be able to handle specified guaranteed band(cid:173)
`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
`45 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(cid:173)
`trol (MAC) layer schedules packet transmission of various
`ss 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
`60 size (TESS), and optionally queue fill levels. These first
`embodiment(s) also further refine the selection process using
`backlog memories corresponding to previously unmet guar(cid:173)
`anteed and/or fair transmission rates. In second embodiment
`(s), memory requirements are reduced by selecting a TFC
`65 based on guaranteed rate transmission rates, QoS class,
`TESS, and queue fill levels, without accommodating back(cid:173)
`logs corresponding to previously unsatisfied requirements.
`
`Page 8 of 20
`
`
`
`US 6,850,540 Bl
`
`3
`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 5
`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(cid:173)
`tiple flows.
`In certain second embodiment(s), a scheduling method for 15
`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(cid:173)
`nels; ascertaining a guaranteed rate transmission rate for
`each channel; ascertaining a queue fill level of a queue that 20
`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- 25
`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 30
`described embodiments are provided for purposes of illus(cid:173)
`tration and understanding and that numerous equivalent
`embodiments are contemplated herein.
`
`10
`
`4
`particular circuits, logic modules (implemented in, for
`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(cid:173)
`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(cid:173)
`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(cid:173)
`plary next-generation system with which the present inven(cid:173)
`tion may be advantageously employed is illustrated gener(cid:173)
`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-
`35 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
`40 "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(cid:173)
`mission time interval (e.g., 10, 20, 40, or 80 ms). Several
`transport channels (e.g., FACHs) are in turn mapped at the
`45 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
`60 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(cid:173)
`mation to the MAC-c PDUs to form FACH FP PDUs which
`are transported to the Node B 150 over an AAL2 (or other
`65 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.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`A more 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(cid:173)
`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 50
`between entities in the exemplary second layer architecture
`of FIG. 3;
`FIG. 5 illustrates an exemplary environment for schedul(cid:173)
`ing data flows in accordance with the present invention;
`FIG. 6 illustrates an exemplary method in flowchart form 55
`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
`
`Page 9 of 20
`
`
`
`US 6,850,540 Bl
`
`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), 5
`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 10
`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(cid:173)
`cated a low QoS should be transmitted over the air interface
`at a lower priority. Priorities may be determined at the MAC 15
`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 20
`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 25
`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 30
`(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 35
`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 40
`packets for transmission on the FACH are associated with
`either a Dedicated Control CHannel (DCCH) or to a Dedi(cid:173)
`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 45
`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 50
`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 55
`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 60
`logical channel data and a MAC header containing, inter
`alia, a logical channel identifier. The MAC-d entity passes
`the MAC SD Us 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 65
`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(cid:173)
`nications network and in particular, though not necessarily,
`to data transmission in a UMTS.
`As noted hereinabove, the 3GPP is currently in the
`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(cid:173)
`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(cid:173)
`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
`
`Page 10 of 20
`
`
`
`US 6,850,540 Bl
`
`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 5
`(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 10
`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 15
`packets in a single TTL 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(cid:173)
`tion (TFC). An example of a TFC is {TF1=(80, 80), TF2= 20
`(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 25
`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 30
`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- 35
`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 40
`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 45
`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 50
`TFs. An example of this would be a,TFCS as follows [ { (80,
`0), (80, O)}, { (80, 0), (80, 80)}, { (80, 0), (80, 160)}, { (80,
`80), (80, 0) }, { (80, 80), (80, 80) }, { (80, 160), (80, O)} ],
`where the transport format of transport channel "1" is given
`as the first element of