US006993041B2
`
`(12) United States Patent
`Yamamoto
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 6,993,041 B2
`Jan. 31, 2006
`
`(54) PACKET TRANSMITTING APPARATUS
`
`6,888,841 B1 *
`2002/0110086 A1*
`
`5/2005 Ozaki ....................... .. 370/413
`8/2002 Reches ..................... .. 370/235
`
`(75)
`
`Inventor: Kanta Yamamoto, Kawasaki (JP)
`
`FOREIGN PATENT DOCUMENTS
`
`(73) Assignee: Fujitsu Limited, Kawasaki (JP)
`
`( * ) Notice:
`
`Subject. to any disclaimer, the term of this
`patent 1S extended or adjusted under 35
`U.S.C. 154(b) by 937 days.
`
`JP
`JP
`
`08251192
`11346246
`
`11275151
`JP
`* Cited by examiner
`
`9/1996
`12/1999
`
`1/2000
`
`(21) APPL N05 09/864995
`.
`1 C I
`F l d
`
`Ely
`,
`M 24 2001
`
`(22)
`
`Primary Examiner—Franl< Duong
`Assistant Examiner—Michael J. Moore
`74 Attorney, Agent, or Firm—Katten Muchin Rosenman
`LLP
`
`(65)
`
`Prior Publication Data
`US 2002/0097733 A1
`Jul. 25, 2002
`
`(57)
`
`ABSTRACT
`
`Disclosed is a packet transmitting apparatus for transmitting
`packets belonging to a plurality of groups having priorities
`figflffieigngfgiiaggeiippaarzgligfifige::i‘3”‘}‘;:
`generating queues on a per-group basis and giving a packet
`.
`.
`.
`.
`.
`.
`transmit pr1v1lege in order, in accordance with the round-
`robin method to elements constituting each of the queues
`queue by queile; and a packemransmfi group decision unit:
`which is provided in the scheduling unit, for deciding that a
`packet transmit group is a group having the highest priority
`among groups in which a packet corresponding to at least
`one queue element is awaiting to be transmitted. The queue
`controller gives the packet transmit privilege to the highest-
`priority queue element of a queue of the packet transmit
`group that has been decided and transmits the packet that
`corresponds to this queue element.
`
`(30)
`Foreign Application Priority Data
`Jan. 24, 2001
`(JP)
`............................. 2001-015615
`(51)
`Int. Cl.
`(200601)
`H04L 12/28
`.370/413; 370/395.43; 370/230.1
`.... ..
`(52) U..S. Cl.
`.......
`(58) Fleld of Classlficatlon Search “““ “ 370/229_238’
`370/412-419
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`............ .. 709/232
`5,838,922 A * 11/1998 Galand et al.
`.
`370/375
`6,570,873 B1 *
`5/2003 Isoyama et al.
`6,667,984 B1 * 12/2003 Chao etal.
`. . . . . .
`. . . .. 370/414
`6,771,596 B1 *
`8/2004 Angle et al.
`.............. .. 370/229
`
`
`
`8 Claims, 13 Drawing Sheets
`
`10
`__
`..
`,:..,
`PACKET TRANSMUTMB APPARATUS‘
`
`25
`
`EGRESS~
`SIDE
`QUEUJNG
`UNIT
`
`26
`
`12
`OUTPUT
`
`I
`INTERFACE
`UNIT
`
`
`ERICSSON EXHIBIT 1006
`
`24
`
`SCHEDULING
`UNIT
`
`"I
`
`I
`
`I J IJ
`
`236‘
`lNGRESS—SIDE
`OUEUJNG UNIT
`
`I
`
`GSHBUFTER
`CLS BUFFER
`_:I
`BE BUFFER
`
`Spare BUFFER
`
`+r)n\mr%Dwo
`
`oar“
`
`GBFD4
`
`:23h
`____..__._,____1
`lNGRESS—SII.)E
`(IUEUING UNIT
`
`GS E30? FER
`INPU T / SIDE
`
`UNIT
`ms BUFFER
`JN FERFACE
`FORWARDING
`II
`03%’
`BE BUFFER
`
`
`
`QBFM
`
`Spare BUFIIZR
`
`

`
`U.S. Patent
`
`Jan. 31, 2006
`
`Sheet 1 of 13
`
`US 6,993,041 B2
`
`
`
`_mE$_<&<ozE_2mz<EBEE
`
`
` moanSn_z__HHEEkammowrwmo___.3W_..__:i._,m.m
`:1”1__2%.U2._c__1#5_.U.EtnaBa:75moE.,.m:z__cz_o~_E§E
`w.....................:1.__...........................
`......................-i__.|:..::;w.:«..l:.w.:l
`
`
`
`Immmmcmu‘:.i:.f:1I..i:.I.:I:ui1:1|};inI............................--__.7........in.:..mo<¢7~_m:z_c7@m_W.ww.o.4”!a_|_:_j._.Da.rDO
`
`
`--.t;_.fi__¢1$52ma,SEQ.o
`.u:2:..W.,
`
`wm_3_,%.%___.5.S.uEa___oz_._:$.m%_:2:
`
`
`ozsmscCNNo_N_H.mo_m-m$moz_H__a{£0.21..................--LU
`—1zrIIK.Ils.IIQIIi:IlIIIauiI:1III1I!vzI:xIxv%|«IEIIi:c!InI:1iuntil;
`
`
`
`
`

`
`U.S. Patent
`
`Jan. 31, 2006
`
`Sheet 2 of 13
`
`US 6,993,041 B2
`
`FIG. 2
`
`PKT
`
`IP PACKET
`
`8
`
`(P PACKET
`
`IN-
`
`APPARATUS
`
`HEADER
`
`PACKET LENGTH
`,. _ _ . . . . . — . — ~ — — — — — — — — — — — — — — - — — . _ n _ _ — . . . _ . _ —_
`
`MULTICAST OUTPUT PORT
`
`iGS : Guaranteed Service
`
`ICLS : Controlled Load Service
`
`
`
`T """""" “.gE:2g;;;gfa;;1""""""""" “
`
`- — . . . . . _ _ . a . . -..-.....__--_--_-------.........._.._.-_.-
`
`ESPARE : SPARE
`
`

`
`U.S. Patent
`
`Jan. 31, 2006
`
`Sheet 3 of 13
`
`US 6,993,041 B2
`
`FIG‘. 3
`
`b
`
`
`
`SECTION
`
`
`
`
`
`1
`
`Q_o
`H
`g
`
`P
`
`
`
`
`:
`1
`1'
`1G8 Rote TH 31 e1
`I
`’ I ‘
`I 3182
`331lg::3‘»‘aL§S“IT?2
`
`1
`es
`!
`11 3194
`i
`;
`.
`1
`,
`i
`:
`
`I i
`
`.5
`
`A
`
`i i
`
`33
`1
`5
`1
`:
`O ,
`!
`X
`
`3
`!
`
`:
`I
`=
`1
`;
`
`PORT—0
`R12
`3‘
`310
`PORT SUPPORT R“ — 1NH<x4>
`
`3 1 a
`C4
`""-
`R
`Reg
`ReQUeSt
`..,.,,...
`6W4,
`
`6“ <x4»
`E
`3’
`.
`C,
`ii Uhnlné
`.
`5; I
`z
`I-1+ A
`5 4 an
`2:
`QBF03
`2 ,
`Queue-iSpare
`o_
`QBF 04
`_
`CRT 1.
`1-5 Q:
`PORT SUPPORT
`g_ 1-
`2 g 5 SECT1ON
`E D__ K
`50%, ‘
`E LL
`
`31h
`
`31 1
`Request(x4)
`G,a,,t(x4;
`
`Rotate
`
`310
`
`317
`
`1
`PORT-7
`‘ PORT SUPPORT
`MI
`31a
`SECTJON
`‘NH (X41
`114 Raq
`ReQU9St (X4)
`'..-='.-.==: mm
`----1...} M»
` ; CONTINUOUS
`31c
`311
`on-|'\
`I
`,__
`«BF
`= T“
`'
`0:
`THD(;:1\txer :: Load
`71
`8
`_GS
`0
`.
`.
`E ,
`O I 0852
`. om ;
`E IHIIIE
`COUNTER: Counter:
`'__
`L--- _4
`3 I
`|—l
`.
`311
`4 an
`-‘
`‘F3 951:,
`LL}
`3
`.
`ear ,4
`
`1
`
`I
`
`I 1GS Rotate TH1
`
`otate 1x4)
`31 e1
`31 2
`1CLS Ro 8
`I
`3183
`1BERoIate 11-13
`I
`l—————-——| 3,
`1SnareRotate TH4
`94
`
`
`
`Stop
`
`I
`
`QZ1
`
`x0<
`
`2:
`1:;
`
`

`
`U.S. Patent
`
`Jan. 31, 2006
`
`Sheet 4 of 13
`
`US 6,993,041 B2
`
`SCHEDULER
`__
`
`
`5 3NH (,4) _ 3
`
`5
`1 32am
`__,_____,___
`to
`‘
`POICHOZ
`Port~1 {
`
`
`P e w ,
`
`
`
`i
`
`'°f' 3:
`
`32604
`
`
`
`
`{NH (X4)
`to
`Pm_8 {(__,
`
`3261
`TH Over Det
`32e72—.
`TH Over Det
`
`
`
`32am
`
`
`
`
`TH Over Det
`
`
`E
`:
`
`TH Over Det
`
`W .................
`
`
`
`
`
`—— ——————~
`32f
`
`32am
`
`——~——
`
`
`
`UJ
`E
`EE
`
`.J
`
`‘z‘
`35
`;
`Lu0I-
`
`—
`from
`each Queue {
`
`
`GROUP
`SETTING
`UNIT
` GROUP
`ELEMENT
`
`A8SOLUTE—
`
`PFUORITY
`DECISION UNIT
`
`
`
`
`
`Rmate
`
`Priority-I
`Round~Robm
`
`
`
`

`
`U.S. Patent
`
`Jan. 31, 2006
`
`Sheet 5 of 13
`
`US 6,993,041 B2
`
`FIG. 5/1
`
`
`
`
`
`NUMBER .
`
`I
`Po-GS ~ P7-GS a
`
`FIRST PRIORITY GROUP
`
`SECOND PRIORITY GROUP
`
`THIRD PRIORITY GROUP
`FOURTH PRIORITY GROUP
`
`
`
`
`
`
`
`
`
`
`
`
`
`Po-BE ~ P7“-BE E
`Po-Spare ~ P7-Spare fl
`
`FIG. 55’
`
` PRIORITY GROUPS
`
`
`
`PORT NO. & 008
`
`
`FIRST PRIORITY GROUP
`
`SECOND PRIORITY GROUP
`
`
`
`
`THIRD PRIORITY GROUP
`
`FOURTH PRIORITY GROUP
`
`

`
`U.S. Patent
`
`Jan. 31, 2006
`
`Sheet 6 of 13
`
`US 6,993,041 B2
`
`FIG 6/!
`
`

`
`U.S. Patent
`
`Jan. 31, 2006
`
`Sheet 7 of 13
`
`US 6,993,041 B2
`
`Eon.
`
`zofimzzoo
`
`28.2%.
`
`Em
`
`a$%z_V:22ozsmso
`
`
`
`:o:mo:_mmm_...Exomm
`
`3..
`
`oemcmmc_E§:2
`
`
`
`:2:oz_E§EE
`
`
`
`:2:ozzgfizom
`
`Q:E2
`
`55¢ax
`
`Sm
`
`Exam.
`
`
`
`a$%z_V._._z:ozsmso
`
`:23oz_am<;w_E
`
`
`msucm
`
` m:_t..m>>._3a:e:moc_8m_oExec;
`
`:23ozszfizom
`
`EXTERNAL INTERFACE
`
`EXTERNAL INTERFACE
`
`
`

`
`U.S. Patent
`
`Jan. 31, 2006
`
`Sheet 8 of 13
`
`US 6,993,041 B2
`
`FIG. 8 PRIOR ART
`
`1 3
`- APPLICATION SERVER
`
`HIGHEST
`TRANSMITTED FERST
`
`PRlORiTY PACKET
`
`_
`
`P~3
`
`7/la
`
`VI/I.
`
`VIII,
`
`2 ROUTER
`
`;%§
`
`11
`
`

`
`U.S. Patent
`
`Jan. 31, 2006
`
`Sheet 9 of 13
`
`US 6,993,041 B2
`
`F/G.
`
`.9 P/9/0/? /4/?7'
`
`3 APPUCATION SERVER
`
`WEEL,.
`
`HIGHEST
`PRlORiTY PACKET
`TRANSMITTED FIRST
`
`2 ROUTER
`
`
`
`
`

`
`U.S. Patent
`
`Jan. 31, 2006
`
`Sheet 10 of 13
`
`US 6,993,041 B2
`
`FIG. 70 PRIOR ART
`
`3 APPLICATION SERVER
`
`CLENT
`
`FIG 7 7 PRIOR ART
`
`SERVER
`
`FRST PHY$CALCHANNEL
`
`CD11
`
`

`
`U.S. Patent
`
`Jan. 31, 2006
`
`Sheet 11 of 13
`
`US 6,993,041 B2
`
`FIG 12 PRIOR ART
`
`FOEWAROi§*$G AT §v§N§?vE5J?v? PACKET SLZE { S4 BYTE8}
`
`..........
`
`$@@@@@—-» ,
`mgm FORWARDING A1.” zmxxsmum PACKET $225 (1522 ewes:
`
`EC} ~——~—--—---~—---—-—----~«’[::-.*“—~'-:-°‘—‘g@3 "’
`
`
`32
`
`CHEN?
`
`;
`
`DATA FROM CUENT
`@
`A
`DAT ?~'RCvf\£ OLSEN?’
`
`
`
`@§
`
`

`
`U.S. Patent
`
`Jan. 31, 2006
`
`Sheet 12 of 13
`
`US 6,993,041 B2
`
`F/G. /3 PRIOR ART
`
`1
`
`F
`
`FOWARDIG A MINIUM ACKT SIZ ( 6 BYTS D
`
`-3 2
`CUENT
`FORWARDING AT MAXTMUM PACKET STZE U 522 BYTES )
`\‘
`-—)
`IE ‘ilk
`
`U
`DEJDCJD-+2F§H
`SEGMENTED INTO FIXED LENGTHS
`
`
`
`
`
`
`
`
`
`TIE —> EEFTEEET
`PACKET REASSEMBLY
`
`DATA FROM CLIENT 11...)
`
`
`A
`
`DATA FROM CLIENT 12->
`
`
`VIIA
`
`

`
`U.S. Patent
`
`Jan. 31, 2006
`
`Sheet 13 of 13
`
`US 6,993,041 B2
`
`
`
`4:2:So-a<m_mEgg:2ED.mialllw
`
`.3,.DD1%WE_a25:0>_nEmmmmmm3pzujo/3_.z
`
`
`
`om|\
`
`,529mzwo
`
`Magoogm./g“.0Ba
`
`
`f|41i1:|J.I|.\
`
`
`.\
`
`4.
`
`EDDDD,TA
`2530znemmmmmm2HZMID/1Hz
`
`
`
`
`
`:2:ozzsazom
`
`
`
`.52ME93zazflé
`
`
`
`Es,QQEQ3GE
`
`
`
`oommoz:O._.<._.<Q
`
`azznfizommm
`
`_“u1
`
`
`
`4A-aflEDGE_95:02nEmmm$mI._.Zm=u_O:Hz
`
`
`
`28.25535$
`
`
`
`\mow26:0>_gEommamx2Hzmjo,3b2
`
`
`
`
`
`
`
`
`

`
`US 6,993,041 B2
`
`1
`PACKET TRANSMITTING APPARATUS
`
`BACKGROUND OF THE INVENTION
`
`This invention relates to a packet transmitting apparatus
`for transmitting, in order, packets belonging to a plurality of
`groups having priorities that differ from one another. More
`particularly, the invention relates to a packet transmitting
`apparatus such as an IP router or Ethernet switch for
`switching variable-length packets.
`When IP networks (the Internet) first appeared, there was
`no differentiated processing within the network and there
`was no processing for giving priority to a certain specific
`flow when allocating bandwidth. In the initial form of the
`Internet, bandwidth allocation was on the basis of “first
`come, first served”, and the more data there was to be sent,
`the larger the network bandwidth that was occupied. Sched-
`uling logic, therefore, also was simple FIFO (first in, first
`out).
`However, the era has gradually come to expect that IP
`networks send multimedia information, namely moving
`images and voice, and not just electronic files, e-mail and
`still images. Multimedia information such as moving images
`and voice is traffic in which it
`is anticipated that
`the
`information will be transmitted from the transmission source
`to the transmission destination “at a certain, fixed bandwidth
`and fixed period and without
`loss of data” as the term
`“real-time traffic” attests. Real-time traffic until now has
`
`been traffic in which information is exchanged by so-called
`telephone networks, wherein communication is carried out
`after reserving a fixed bandwidth from the transmission
`source to the transmission destination.
`
`The enormous amount of packet data from an ever
`increasing number of Internet users has led to packet con-
`gestion within the network and many packets are now
`starting to be discarded because they cannot be processed in
`the network. Many users are now experiencing a decline in
`throughput to an extent visible to the eye. This has led to
`requests that
`throughput be raised in exchange for the
`payment of fees higher than those paid by other users. This
`is often compared to the difference between a common road
`and a highway. Having a fixed bandwidth assured is equiva-
`lent to travel on a highway, while having various traffic
`scramble for bandwidth is likened to travel on a common
`road. However, it should be noted that in the case of an IP
`network, merely assuring traffic on the highway means
`taking network resources (bandwidth) away from the com-
`mon road, as a result of which the common road becomes
`even more congested.
`The above-mentioned circumstances have resulted in the
`
`need for bandwidth control and priority control in IP net-
`works that aim at effective exploitation of bandwidth by
`statistical multiplexing. Differentiation on the Internet is
`now in the process of being defined and established as
`service policy by QoS (Quality of Service), Diffserve and
`Intserve, etc. With service policy based upon the idea of
`differentiation, services for various packet flows are man-
`aged by packet-flow classification, stipulation of input-
`traffic characteristics, stipulation of packet-discard priority
`and stipulation of bandwidth assurance, etc.
`Strict queuing and weighted fair queuing (WFQ) are
`typical examples of bandwidth control schemes.
`Strict queuing is a simple priority scheme in which if a
`packet is one that has been set to a high priority, the packet
`is always given precedence and sent first. FIG. 8 is a diagram
`useful in describing the simple priority scheme, in which
`numerals 11 to 14 denote clients, 2 a router and 3 an
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`application server. This is for a case where each of the clients
`11 to 14 transmits packets to the server 3 via the router 2,
`where P represents the priority; the larger the value of P, the
`higher the priority. If packets (1) to (4) enter respective ports
`from the clients 11 to 14 simultaneously, the router 2 sends
`the packets to the server 3 in order of decreasing priority
`which, in FIG. 8, is the order (3)e(2)e(4)—>(1).
`FIG. 8 is for the simple case, in which packets are no
`longer transmitted in simple FIFO (first in, first out) order
`when priority control is carried out. In FIG. 9, it will be
`understood that packet (5) is transmitted before packet (1)
`despite the fact that packet (1) arrived before packet
`Thus, with strict queuing, if packets having a high priority
`arrive successively, packets of low priority are not sent until
`the transmission of packets having a higher priority is
`completed. Consequently, the possibility that a packet of low
`priority will remain in a queuing memory is high. If there is
`input beyond a certain threshold, low-priority packets are
`discarded.
`
`Acharacterizing feature of strict queuing is that very strict
`priority control is carried out and scheduling processing also
`is very easy and simple. However, the setting of bandwidth
`and the setting of priority cannot be performed with a high
`degree of freedom between flows.
`Weighted fair queuing is a scheme in which priority ratio
`(weight) is decided using order of priority as an analog
`parameter, and packets are transmitted in accordance with
`the ratio decided. FIGS. 10 and 11 are diagrams useful in
`describing weighted fair queuing. Here clients 11, 12, 13 and
`14 are assigned priority ratios of 12.5%, 12.5%, 25% and
`50%, respectively, with respect to a single port on the server
`3. With weighted fair queuing, bandwidth allocation pro-
`cessing in accordance with the ratios is executed without a
`strict inclination toward a specific priority as in the case of
`strict queuing (see FIG. 11).
`With weighted fair queuing, however, priority-ratio con-
`trol is applied to variable-length packets. When weighted
`control is carried out based upon the number of packets
`forwarded, the difference between packets of minimum size
`and maximum size is not recognized. If an Ethernet frame is
`taken as an example, minimum size is 64 bytes and maxi-
`mum size is 1522 bytes. If router 2 is to send packets from
`clients 11 and 12 alternately to server 3, therefore, as shown
`in FIG. 12, a large difference in which priority-ratio error
`increases almost 24-fold occurs. A method of solving this
`problem is to segment variable-length packets into a fixed-
`length size and perform control based upon the number of
`transfers of fixed-length data, as shown in FIG. 13.
`With this method, however, a problem which arises is that
`a segmenting processor and a reassembly processor are
`required respectively in front of and in back of a routing or
`switching unit (not shown) in the router 2. In particular, it
`must be assumed that a plurality of packets will undergo
`reassembly simultaneously in the reassembly processor,
`logically or physically separate reassembly buffers must be
`provided for each of these packets and the buffers must be
`controlled. FIG. 14 is a diagram useful in describing packet
`transmission control in the router. Shown in FIG. 14 are a
`
`packet switch 2a, a scheduler 2b, reassembly buffers 2C1, to
`2c4 for reassembling packets from each of the clients, and a
`packet read-out unit 2d for reading packets out of the
`buffers.
`
`(1) First Problem
`The weighted fair queuing scheme introduces the concept
`of a virtual clock on a per-packet basis. Avirtual clock is the
`time needed for a packet to be output from a device, i.e., the
`time during which the packet exists in the device. Virtual
`
`

`
`US 6,993,041 B2
`
`3
`clock information must be managed individually packet by
`packet inside the device, and the generation and manage-
`ment of this information entails a great amount of process-
`ing. In other words, the scheduler in weighted fair queuing
`must generate and manage a great deal of complex control
`information for all packets that exist
`inside the device,
`scheduling processing is complicated and processing time is
`prolonged.
`(2) Second Problem
`When a variable-length packet is segmented into fixed-
`length data such as ATM cells and the scheduler also
`performs schedule management in units of the fixed-length
`data, scheduler control is comparatively easy. In order to
`accomplish this, however, processing for segmenting vari-
`able-length packets is required in front of the routing unit
`and switch unit, and reassembly processing is required in
`back of the switch unit. Accordingly, it must be kept in mind
`that a plurality of packets will undergo processing simulta-
`neously in buffers for reassembling a variable-length packet
`in back of the switch unit, and it is necessary that a logically
`or physically separate reassembly buffer be provided for
`each of these packets. Aproblem which arises is an increase
`in the scale of the apparatus.
`(3) Third Problem
`It is desired that physical bandwidth be usable with 100%
`effectiveness. To achieve this, it is required that a variable-
`length packet be output to its destination by stuffing in the
`packet data without leaving needlessly unallocated band-
`width and without any gaps in terms of time. However, with
`a complicated scheduler arrangement, as in the prior art, the
`time for a single scheduling processing cycle is prolonged
`and packet data cannot be output to the output destination
`without gaps.
`(4) Fourth Problem
`The conventional scheduler processes queues, which are
`to undergo scheduling, in a single stage, and the setting of
`priorities also is performed by setting all queue elements
`(e.g., packets) as objects to be scheduled. In the conven-
`tional schemes, the round-robin method is adopted so that a
`grant is made to rotate from one queue element to another.
`The round-robin method is such that if a certain queue
`element acquires a grant, the priority of this queue element
`is reduced to the lowest level in the next cycle of scheduling
`processing. Though the round-robin method is suited to fair
`scheduling, it cannot be employed as is in non-linear band-
`width allocation control (i.e., in differentiated service). For
`example, with regard to queue elements the bandwidth of
`which has been set high, it is necessary to raise the frequency
`with which transmission grants are given. The conventional
`round-robin scheduler, however, cannot perform such sched-
`uling control.
`(5) Fifth Problem
`Physical bandwidth assurance schedulers that handle vari-
`able-length packets are classified broadly into two types.
`One uses a method of performing scheduling by segmenting
`variable-length packet data into fixed-length data, and other
`uses a method of performing scheduling using the variable-
`length packet data as is. The present invention adopts the
`method of performing scheduling using the variable-length
`packet data as is. In this method, a transmission grant from
`a scheduler generally is output in packet units. In this case,
`the length of packet data transferred by a single transmission
`grant is not fixed. In other words, even though a single
`transmission grant
`is rotated equally among the queue
`elements, the same physical bandwidth is not occupied. If
`this takes place several dozen or several hundred times, in
`the worst case bandwidth allocation to the queue elements
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`becomes unfair regardless of the fact that the transmission
`grant is caused to rotate among elements the same number
`of times. This is the reason why bandwidth assurance control
`is difficult in a scheduler that handles variable-length pack-
`ets.
`
`(6) Sixth Problem
`The fifth problem, namely unfairness in the transmission
`of variable-length packets, is eliminated by stipulating the
`transmission assurance bandwidth in a single transmission
`grant. In this case, it is necessary to stipulate processing in
`an instance where a packet to be transmitted ceases existing
`before the assured bandwidth is attained. A method of
`
`waiting for arrival of the packet is available as a method of
`such processing. This is a method of issuing transmission
`grants continuously to queue elements of interest until the
`assured bandwidth is attained. However, 100% utilization of
`physical bandwidth is impossible and the problem of need-
`lessly unallocated bandwidth arises.
`(7) Seventh Problem
`As mentioned above, a variable-length scheduler cannot
`use information indicative of packet transfer count in order
`to implement fair bandwidth allocation. The reason for this
`is as follows: Even if there are the same ten packets of data,
`unfairness occurs, despite an identical bandwidth setting, in
`a case where there are a large number of minimum-size
`packets from one queue element and a large number of
`maximum-size packets
`from another queue
`element.
`Accordingly,
`it
`is necessary to arrange it so that exact
`bandwidth control can be carried out even in the case of
`
`variable-length packets.
`
`SUMMARY OF THE INVENTION
`
`Accordingly, an object of the present invention is to make
`bandwidth control possible, without segmenting variable-
`length packets, by making joint use of strict queuing and
`weighted fair queuing, thereby reducing the scale of sched-
`uler circuitry and raising the speed of processing.
`Another object of the present invention is to adopt, as
`queue elements, combinations of input ports and quality
`classes appended to packets that enter from these ports, and
`perform bandwidth control and priority control in units of
`these queue elements and not
`in packet units,
`thereby
`reducing the scale of scheduler circuitry and raising the
`speed of processing.
`Another object of the present invention is to dispense with
`the need for packet segmenting processing in front of a
`routing unit or switch and packet reassembly processing in
`back.
`
`Another object of the present invention is to so arrange it
`that processing time of a single scheduling cycle is short-
`ened, i.e., so that scheduling processing time will fall within
`the transmission time of minimum-length packets.
`Another object of the present invention is to classify
`queue elements into absolute-priority groups of a plurality of
`stages and give packet transmission privilege to each of the
`queue elements in regular order within the groups by the
`round-robin method,
`thereby raising the frequency with
`which transmission grants are delivered to specific queue
`elements of high priority even by the simple round-robin
`method.
`
`Another object of the present invention is to select a
`priority group by a simple absolute-priority scheme, thereby
`making it possible to execute high-speed scheduling pro-
`cessing by simple hardware.
`Another object of the present invention is to arrange it so
`that queue elements belonging to each priority group can be
`
`

`
`US 6,993,041 B2
`
`5
`set at will and so that no limitation is imposed upon the
`number of these elements, and to make it possible to perform
`bandwidth control even if there is an imbalance in the ratio
`
`of the flowrate of a group having a high priority to the
`flowrate of a group having a low priority.
`Another object of the present invention is to make it
`possible to control bandwidth allocated to each queue ele-
`ment by setting assured bandwidth based upon a single
`transmission grant with regard to each queue element.
`Another object of the present invention is to so arrange it
`that if packets to be transmitted successively no longer exist,
`a transmission grant with regard to the particular queue
`element is rescinded immediately, the transmission grant is
`delivered to another queue element and needlessly unallo-
`cated bandwidth is eliminated in shared physical bandwidth
`so that bandwidth can be utilized 100%.
`Another object of the present invention is to implement
`exact bandwidth control by setting data transmission flow-
`rate (bandwidth) of packets, which are transmitted per
`prescribed period of time, for every quality class (queue
`element) of each input port.
`A first packet
`transmitting apparatus according to the
`present
`invention comprises:
`(1) a queue controller for
`generating a queue for every group of a plurality of groups
`having priorities that differ from one another, and giving
`packet transmit privilege in order to elements constituting
`each of the queues; and (2) a packet-transmit group decision
`unit for deciding that packet
`transmit group is a group
`having the highest priority among groups in which a packet
`corresponding to at least one queue element is awaiting to be
`transmitted; wherein the queue controller transmits a packet,
`which corresponds to a queue element having the packet
`transmit privilege, in the queue of the packet transmit group.
`A second packet transmitting apparatus according to the
`present invention further comprises (3) a group setting unit
`for adopting, as queue elements, combinations of input ports
`and quality classes added onto packets that enter from these
`ports, and setting groups to each of which these queue
`elements belong; wherein the queue controller gives the
`packet transmit privilege, equally and in order in round-
`robin fashion, to each of the queue elements queue by queue.
`A third packet transmitting apparatus according to the
`present invention further comprises: (4) a buffer for storing
`a packet, which is waiting to be transmitted, for every queue
`element; and (5) a request generator for generating a trans-
`mit request signal for every queue element corresponding to
`a buffer in which a packet waiting to be transmitted has been
`stored; wherein the transmit-group decision unit identifies
`groups in which a packet waiting to be transmitted exists
`based upon whether or not there is a transmit request signal
`from at least one of queue elements belonging to each of the
`groups, and decides that a group having the highest priority
`among these groups is the packet transmit group.
`A fourth packet transmitting apparatus according to the
`present invention further comprises: (6) an assured-data-
`quantity setting unit for setting a data transmission quantity,
`which is assured by a single packet transmit privilege, for
`every queue element; (7) a monitoring unit for monitoring
`an actual transmission quantity of a packet corresponding to
`a queue element to which the packet transmit privilege has
`been given; and (8) a control signal generator for outputting
`a control signal, which is for delivering the transmit privi-
`lege to the next queue element, when the actual data
`transmission quantity has become equal to the assured data
`quantity; wherein the queue controller gives the packet
`transmit privilege to the next queue element based upon the
`control signal.
`
`6
`A fifth packet transmitting apparatus according to the
`present invention further comprises: (9) a data-transmission
`flowrate setting unit for setting data transmission flowrate of
`a packet, which is transmitted per set period of time, for
`every queue element; (10) means for monitoring actual data
`transmission flowrate per the set period of time for every
`queue element; and (11) packet-transmit inhibiting means
`for monitoring the actual data transmission flowrate for
`every queue element, and generating a transmit-inhibit sig-
`nal which inhibits transmission of a packet corresponding to
`the queue element, until the set period of time elapses, when
`the data transmission flowrate has become equal to the set
`data transmission flowrate.
`
`The packet transmitting apparatus of the present invention
`transmits a packet through a two-stage arrangement consist-
`ing of processing concerning to which priority group a
`transmission grant is to be issued and processing concerning
`to which queue element of this priority group a transmission
`grant is to be issued. As a result, packet transmission control
`can be performed through a simple arrangement.
`Further, the packet transmitting apparatus of the present
`invention executes scheduling processing, with variable-
`length packet data as is, without segmenting the variable-
`length packet data. As a result, bandwidth allocation control
`can be implemented accurately and freely for every queue
`element, i.e., for every quality class of each port.
`Further, the packet transmitting apparatus of the present
`invention generates a transmit request signal to a scheduler
`in units of the quality class of each input port, not in packet
`units. This makes possible a large-scale reduction in the
`scale of the circuitry as well as an increase in speed.
`Further, the packet transmitting apparatus of the present
`invention does not issue transmission grants in data units
`obtained by segmentation into fixed length but instead issues
`transmission grants in units of variable-length packet data.
`As a result, the packet data per se can be forwarded without
`being segmented and there is no need for segmentation
`processing for the segmenting of variable-length packets and
`for reassembly processing.
`Further, the packet transmitting apparatus of the present
`invention is such that the scheduler is implemented by
`hardware. This makes high-speed scheduling decisions pos-
`sible so that the time for a single scheduler decision can be
`kept within the time needed for physical transmission of
`minimum packet length. As a result, delay due to scheduler
`processing is reduced so that even if packets of the minimum
`packet size have been input successively, it is possible to
`transmit packets successively while eliminating physically
`idle bandwidth.
`
`Further, the packet transmitting apparatus of the present
`invention is so adapted that a priority group can be set freely.
`This makes it possible to deal with a situation in which the
`ratio of the number of queue elements of high priority to the
`number of queue elements of low priority is not in balance.
`Further, the packet transmitting apparatus of the present
`invention is such that a packet conforming to a queue
`element to which a transmission grant has been issued is
`given the grant until the assured transmission bandwidth is
`exceeded. As a result, even if the apparatus is of the
`packet-by-packet type, physical bandwidth assurance (bytes
`per second or bits per second) is possible in a single
`transmission grant. Further, if transmission of all packets is
`completed before the actual used bandwidth becomes equal
`to the assured transmission bandwidth,
`the transmission
`grant is rescinded immediately, thereby making it possible to
`prevent the occurrence of wasteful physically idle band-
`width.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`

`
`US 6,993,041 B2
`
`7
`Further, the packet transmitting apparatus of the present
`invention basically is a round-robin scheduler for simple
`priority control. However, by adopting an arrangement in
`which packet-by-packet flowrate information is fed back,
`high-speed scheduling processing implemented by hardware
`becomes possible. Moreover, control for absolute allocation
`of physical bandwidth becomes possible in units of bytes per
`second or bits per second.
`Other features and advantages of the present invention
`will be apparent from the following description taken in
`conjunction with the accompanying drawings, in which like
`reference characters designate the same or similar parts
`throughout the figures thereof.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a block diagram illustrating a packet transmitting
`apparatus according to the present invention;
`FIG. 2 is a diagram showing the structure of a header in
`the apparatus;
`FIG. 3 is a diagram (part 1) showing the details of a
`scheduling unit;
`FIG. 4 is a diagram (part 2) showing the details of the
`scheduling unit;
`FIGS. 5A and 5B show examples of priority groups;
`FIGS. 6A and 6B are diagrams useful in describing the
`round-robin method;
`FIG. 7 is a diagram showing the overall structure of a
`packet switching device according to the present invention;
`FIG. 8 is a diagram useful in describing a simple priority
`scheme according to the prior art;
`FIG. 9 is a diagram useful in describing another simple
`priority scheme according to the prior art;
`FIG. 10 is a diagram useful in describing a weighted fair
`queuing scheme according to the prior art;
`FIG. 11 is
`a diagram useful
`in describing another
`weighted fair queuing scheme according to the prior art;
`FIG. 12 is a diagram useful in describing problems with
`the weighted fair queuing scheme according to the prior art;
`FIG. 13 is a diagram useful in describing a method of
`solving the problems with the weighted fair queuing scheme
`according to the prior art; and
`in describing problems
`FIG. 14 is a diagram useful
`encountered with the method of FIG. 13.
`
`DESCRIPTION OF THE PREFERRED
`EMBODIMENTS
`
`(A) First Embodiment
`(a) Overall Structure of the Packet Transmitting Appara-
`tus
`
`FIG. 1 is a block diagram illustrating a packet transmitting
`apparatus 10 according to the present invention. This packet
`transmitting apparatus is such that when packets are to be
`transmitted to a transmission line, the transmission is made
`in accordance with predetermined scheduling on the basis of
`input ports PO to P” at which the packets arrive and the
`quality classes of the input