home *** CD-ROM | disk | FTP | other *** search
/ ftp.ee.lbl.gov / 2014.05.ftp.ee.lbl.gov.tar / ftp.ee.lbl.gov / cbq2.0g.tar.Z / cbq2.0g.tar / README-cbq-use
Text File  |  1998-07-06  |  14KB  |  280 lines
  1.  
  2. This note is intended to clarify how to use Class-Based Queueing (CBQ) in
  3. combination with RSVP.  It is assumed that the reader of this document is
  4. familiar with the contents of the the documents mentioned in the
  5. reference section below.
  6.  
  7.  
  8. Introduction:
  9. ============
  10.  
  11. In providing resource management facilities for the gateway, CBQ
  12. presents a number of management features as well a variety of operating
  13. modes.  This document provides a brief overview of each of these
  14. features.  For more detailed information on CBQ and its implementation,
  15. please visit:
  16.  
  17.     http://www-nrg.ee.lbl.gov/cbq.html
  18.  
  19. Principles of Operation:
  20. ========================
  21.  
  22. As a link-sharing mechanism, CBQ presents the gateway with new
  23. functionality for resource management.  First and foremost, CBQ
  24. introduces the notion of allowing multiple agencies, protocol families,
  25. or traffic types to share the bandwidth of a given network link.
  26. Furthermore, using the same set of mechanisms, CBQ implements the
  27. traffic control capabilities that are required to implement IETF's
  28. Intergrated Services models.  Many of the features and functionality
  29. are enabled via a configuration file whose syntax and definition are
  30. discussed later in the document.
  31.  
  32. One of the primary goals of CBQ is to allow each leaf and interior
  33. class of the link sharing structure to receive its allocated bandwidth
  34. over some appropriate time interval given sufficient demand.  Secondly,
  35. if all classes have received their allocated bandwidth, the
  36. distribution of any "excess" bandwidth should follow some set of
  37. reasonable guidelines.  To acheive the aforementioned goals, the CBQ
  38. framework decomposes the problem of resource management into two types
  39. of scheduling functions: a link-sharing scheduler and a generalized packet
  40. scheduler.  The link-sharing scheduler is responsible for maintaining
  41. link-sharing constraints within a link-sharing structure.  The generalized
  42. packet scheduler will differentiate service between packets based on other
  43. requirements such as delay, jitter, and loss.
  44.  
  45. This CBQ implementation contains a variety of features.  The feature list
  46. includes top-level link-sharing scheduler, packet-by-packet round robin
  47. (PRR) packet scheduler, and weighted round robin (WRR) packet scheduler.
  48.  
  49. As described in [1], the top-level link-sharing scheduler approximates
  50. that of the formal link-sharing scheduler without the computational
  51. complexity of formal link-sharing.  Top-level link-sharing uses a
  52. hueristic called "top-level" to maintain link-sharing constraints.
  53. This "top-level" hueristic refers to the depth of the link-sharing
  54. structure to which a given traffic class may borrow bandwidth.  Rules
  55. for setting the "top level" heuristic can be found in [1].  In
  56. top-level link-sharing, a traffic class may continue to emit traffic in
  57. a unregulated fashion, under the following conditions:  the traffic
  58. class is not overlimit; the traffic class has an underlimit ancestor
  59. whose level is atmost "top-level".  If neither condition is true, then
  60. the class is overlimit and must be regulated.  Currently, packets of an
  61. overlimit class are dropped, if sufficent backlog builds up.  Other future
  62. strategies might include re-classification of the packet.
  63.  
  64. Other features of this CBQ implementation include two generalized
  65. packet schedulers, PRR and WRR.  In both cases, the scheduling
  66. algorithms employ priority based scheduling. In this scheme, packets
  67. are sent from the highest priority level first. Where the packet
  68. schedulers differ is with regard to how the packets are scheduled
  69. within a priority level. For PRR, plain round-robin scheduling
  70. arbitrates between traffic classes in the same priority level.  The WRR
  71. scheduler differs in that it employs weights proportional to a traffic
  72. class' bandwidth allocation. The weight determines the number of bytes
  73. that a traffic class is allowed to send in a scheduling round.  If a
  74. packet to be transmitted by the WRR scheduler is larger that the
  75. class's weight, and the class is underlimit (via link-sharing
  76. constraints), then the packet is sent.  This allows the traffic class
  77. to borrow ahead from its weighted allotment for future rounds of the
  78. round-robin.
  79.  
  80. In an example link-sharing structure with a root class and 3 child
  81. classes (classes A, B, and C), CBQ will enfore link-sharing rules such
  82. that each child class gets its respective bandwidth.   If, for example,
  83. class B does not offer any traffic load, then classes A and C are free
  84. to borrow the excess bandwidth that class B is not using. Once class B
  85. starts offering load, then classes A and C will halt borrowing class
  86. B's bandwidth.  Borrowing for a given traffic class is enabled via the
  87. configuration file. In order for a class to borrow bandwidth, the
  88. "borrow" parameter in the configuration file for the borrowing class
  89. must be set to its parent. Equally, the "root" class of this
  90. link-sharing structure represents the entire link.  Therefore, the
  91. "root" class never will have packets queued behind it.  Only leaf
  92. classes will have traffic queues. A minimal link-sharing structure is
  93. described below.
  94.  
  95. Finally, a work-conserving mode called "efficient" mode is included
  96. in this CBQ implementation.  "Efficient" mode enables CBQ to send a packet
  97. From an overlimit class if all classes of the link-sharing structure
  98. are overlimit.  This effectively enables CBQ to adjust to real network
  99. conditions.  For example, if the target interface link speed is
  100. 5,000,000 bits/second in a shared ethernet environment, CBQ will use
  101. that 5Mbits and then some if the  environment is lightly loaded.
  102. Hence, CBQ will allow all classes to grab extra network capacity when
  103. the network is lightly loaded.  Conversely, if the network becomes
  104. heavily loaded, CBQ will adjust itself accordingly.  The same will hold
  105. true about the efficient mode in half-duplex switched environments.
  106. There are, however, some implications of using this mode.  "Efficient"
  107. mode will allow some traffic classes to get an "unfair" portion of the
  108. "excess" bandwidth.  Hence, the "excess" bandwidth may not be shared
  109. equally with other classes of the link-sharing structure.  But, other
  110. traffic classes in the link-sharing structure will continue to receive
  111. their allocated bandwidth.  In general, great caution should be used
  112. in employing "efficient" mode.  Only in situations where "fair" sharing
  113. of excess bandwidth is not a principle concern should "efficient" mode
  114. be enabled.
  115.  
  116. Know Limitations:
  117. ================
  118.  
  119. This CBQ implementation is still maturing.  There are some known limitations
  120. with this implementation.  First, this CBQ implementation requires the
  121. use of modified ethernet drivers to enable CBQ to receive the appropriate
  122. feedback to operate properly.  A future version of Solaris will incorporate
  123. appropriate feedback mechanisms such that hand crafted drivers are not
  124. required.  Next, the CBQ implementation has not been tested thoroughly on
  125. a large set of traffic classes.  Next, it is believed that link-sharing
  126. configuration of 200 or more traffic classes will cause unpredictable results
  127. with this CBQ implemtation.   This issue is under examination and improvements
  128. will be made available at a future date.
  129.  
  130. Finally, CBQ is a packet scheduler for the local host interface.  It is
  131. not the traffic control mechanism for a shared access network. To
  132. obtain quality of service in a shared access network, the network, one
  133. needs RSVP, CBQ (or some other packet scheduler), and the switches/hubs
  134. need to implement something like SBM[2] and IEEE 802.1p.  In general, CBQ
  135. can serve as the network traffic control mechanism in point-to-point style
  136. networks such as T1 lines, PPP over Sonet, ISDN or dial-up PPP links.
  137.  
  138. Configuration file:
  139. ===================
  140.  
  141. The ensuing sections define the syntax of the configuration file and how
  142. to parameterize some of the parameters.  More detailed information on setting
  143. parameters can be found in [4].
  144.  
  145. Interface Specification:
  146. =======================
  147.  
  148. The syntax of the interface specification is as follows:
  149.  
  150. interface <interface type> bandwidth <b> cbq|cbq-wrr [stats] [efficient]
  151.  
  152. <interface type> specifies the interface name for which to enable CBQ.
  153. Currently, hme, le, qe, ifppp, and ipdptp are supported.
  154.  
  155. Bandwidth <b> is the target link bandwidth.  For some environments, such
  156. as shared ethernet, this may vary because of the nature of the medium.
  157. For full-duplex switched ethernet environments, this tends to be full
  158. link speed of the ethernet interface.
  159.  
  160. <cbq|cbq-wrr> is the selection the packet scheduler to be used.
  161. Current choices include: "cbq" and "cbq-wrr".  "CBQ" selects CBQ's
  162. packet-by-packet round robin scheduler, whereas, "cbq-wrr" selects
  163. CBQ's weighted round robin scheduler.
  164.  
  165. [Efficient] mode enable is the selection of putting CBQ into a
  166. work-conserving mode.  The keyword "efficient" will enable CBQ to send
  167. a packet from an overlimit class, if all classes of the link-sharing
  168. hierarchy are overlimit.
  169.  
  170. [Stats] enable puts CBQ into a primitive statistical collection mode.
  171. This is primarily used for debugging purposes.  The output of this mode
  172. is sent directly to /dev/console.
  173.  
  174. Class Specification:
  175. ===================
  176.  
  177. For the class specification, the following syntax is used:
  178.  
  179. class <scheduler> <interface type> <class-name> <parent-class-name|NULL>
  180.        [priority <sched-pri>] [pbandwidth <p>] \
  181.        [admission predictive|guaranteed|none] \
  182.        [borrow <borrow_class>] \
  183.        [maxburst <burst count>] [packetsize <size>] \
  184.        [default]
  185.  
  186. <Scheduler> is the packet scheduler that this class definition it be
  187. associated with.  Currently, "cbq" and "cbq-wrr" are the choices.
  188.  
  189. <Interface type> is the interface that the class will be created on.
  190.  
  191. "Class name" is the name of the class.
  192.  
  193. <Parent classname> is the name of the parent class of this class.
  194. The root class does not have a parent class. Hence the parent class is
  195. "null".  All other classes MUST have a parent class.
  196.  
  197. <Priority <p>> is the class priority for the CBQ schedulers for both
  198. WRR and PRR.  Maximum priority is 7. Lowest priority is 0.
  199.  
  200. <Pbandwidth <bandwidth>> is the percentage of the interface bandwidth to
  201. be assigned to this traffic class.  Generally, the sum of each pbandwidth
  202. parameter for all classes other than the root class should add up to the
  203. pbandwidth parameter of the root class.
  204.  
  205. [Admission <cntlload|none>] is the type of admission control and QoS type
  206. RSVP is to provide to the class. Currently, "cntlload" and "none" are
  207. the only valid admission types.  If the value is "none", RSVP will not
  208. classify flows to this class. If the value is "cntlload", then RSVP
  209. will classify Controlled Load Service flows as defined in [3] to this class.
  210.  
  211. [Borrow <borrow_class>] enables borrowing for the class. If the class
  212. is not to borrow bandwidth, then a borrow definition should not be
  213. defined. The class name for borrowing MUST be that of the parent class
  214. for the class.
  215.  
  216. [Maxburst <burst>] specifies the maximum back-to-back packet burst
  217. allowed for the traffic class.  Maximum burst should be set such that
  218. it is larger than the maximum token bucket depth for any RSVP flows
  219. that will be mapped to the traffic class. The default is 20 packets.
  220.  
  221. [Minburst <burst>] specifies the minimum waiting time for an overlimit
  222. class.  This defines, in average sized packet times, how far into the
  223. future the class will need to wait before being able to send traffic
  224. again.  The default for "minburst" is 2.
  225.  
  226. <Packetsize <size>> is the expected average packetsize for the the
  227. class.  The default value is 1000 bytes.
  228.  
  229. [Default] defines the class to be where all unclassified (usually the
  230. best-effort) traffic will be placed.  Every link-sharing structure MUST
  231. have a "default" traffic class.
  232.  
  233.  
  234. Samples Configurations:
  235. ======================
  236.  
  237. The minimum link-sharing structure that one can define is a structure
  238. with a root class and a child class that is the "default" class.
  239. Thus, the example below is the absolute minimum configuration in order
  240. for CBQ to work properly:
  241.  
  242. interface le0 bandwidth 10000000 cbq
  243. class cbq le0 root_class NULL priority 3 admission none pbandwidth 100
  244. class cbq le0 data_class root_class priority 3 pbandwidth 100 default
  245.  
  246. Now for more sophisticated configurations, other parameterizations of
  247. class hierarchies can be configured. For example, a partitioning of the
  248. a link that will have Controlled Load traffic and best effort traffic
  249. might look like:
  250.  
  251. interface le0 bandwidth 10000000 cbq-wrr
  252. class cbq le0 root_class NULL priority 3 admission none pbandwidth 100
  253. class cbq le0 res_class root_class priority 7 pbandwidth 20 
  254. class cbq le0 unres_class root_class priority 3 pbandwidth 80 default
  255.  
  256. In the above example each child class get 20% and 80% of the link
  257. bandwidth respectively.  Neither will get to borrow bandwidth unless
  258. borrowing is enabled.  If borrowing is enabled for both of the
  259. children, then each class may borrow all "excess" bandwidth that is
  260. available.
  261.  
  262. References:
  263. ==========
  264.     1.    S. Floyd and V. Jacobson.  "Link-sharing and Resource
  265.         Management models for packet networks."  IEEE/ACM
  266.         Transactions on Networking 3(4), 1995.
  267.  
  268.     2.    R. Yavatkar, D. Hoffman, Y. Bernet, and F. Baker.
  269.         "SBM(Subnet Bandwidth Manager): A proposal for Admission
  270.         Control over IEEE 802-style networks." Internet Draft,
  271.         ftp://ftp.ietf.org/internet-drafts/
  272.         draft-ietf-issll-is802-sbm-04.txt
  273.  
  274.     3.    J. Wroclawski. "Specification of the Controlled-Load
  275.         Network Element Service." RFC 2211, http://www.ietf.org.
  276.  
  277.     4.    S. Floyd and M. Speer.  "Experimental Results for
  278.         Class-Based Queueing.",  Work in progress,
  279.         http://www-nrg.ee.lbl.gov/cbq/
  280.