Abstract:
A method and apparatus for queuing control of variable bandwidth communications channels. The apparatus detects a change from a first bandwidth to a second bandwidth of a communication channel. Finally a quality of service controller is adjusted to compensate for the change from a first bandwidth to a second bandwidth.

Description:
FIELD OF THE INVENTION 
   The present invention relates to a method and apparatus for handling information sent through a digital network and, more specifically, to a method and apparatus of traffic congestion prevention and control within the cell switching network. 
   BACKGROUND OF THE INVENTION 
   Asynchronous Transfer Mode (ATM) or “cell switching” is a method of transmitting digital information wherein the information is broken into equal sized units called “cells.” The individual cells of information are transmitted from a source node to a destination node through a “channel.” A channel is a pathway through a digital network. A digital network is constructed of digital switches coupled together by digital communication channels. 
   A typical full-integrated voice and data network using digital trunk lines (e.g., T1, FT1, E1, T3, etc.) includes a number of geographically distant interconnected nodes. Each node acts as a cell exchanger for receiving and forwarding cell information to its destination. By the use of a variety of interface cards, each node is capable of interfacing with user generated voice and data streams, then segmenting and assembling the streams into a more efficient cell format for transmission over a closed network using digital lines. Each node is also capable of receiving data from other network nodes and forwarding that data through to other network nodes to its ultimate destination. All terminal nodes also provide the necessary interface cards required to reassemble the data contained in the cells into a standard user data stream format. 
   Each cell originates at a source node and is transmitted across a communication channel. The communication channels carry the cells of information between the digital switches along the connection pathway. The digital switches route the cells from incoming communication channels to outgoing communication channels and finally to a destination node. 
   Even with sophisticated queuing and service algorithms, however, congestion (due to excess arriving traffic at a switch) can occur. If no resources are available, the connection is not allowed. 
     FIG. 1  illustrates a typical prior art switch  22  to switch  22  communication scheme. Voice cells of telephone  201  communicate with switch  22  via bidirectional communication links  202 . Voice cells of telephone  201  are transmitted into switch  22  and stored in queue  203 . Voice cells of telephone  201  leave queue  203  and are provided to cell selector  212 . Likewise, workstation  204 , typically via a Large Area Network (LAN) (not shown), passes workstation cells to rate controller  205  to the switch  22  over bi-directional communication links  202 . The workstation cells transmitted into switch  22  are stored in queue  206 . Workstation cells leave queue  206  and are provided to cell selector  212 . 
   Cell selector  212  transmits voice and workstation cells to another switch  22  via bi-directional communication channel  42 . Cell router  207  receives the cells from channel  42 . Cell router  207  delivers voice cells to voice queue  208  and workstation cells to queue  209 . Queue  209  passes the workstation cells on to rate controller  205  which then sends the data to workstation  204 . Voice queue  208  passes the voice cells to telephone  201  via bi-directional communication links  202 . Queues  206  and  209  include congestion controller  210  which provides a feedback signal  211  to rate controller  205 . Rate controller  205  regulates the data rate at which workstation cells are accepted by or delivered from queues  206  and  209 . Thus congestion controller  210  provides variable rate quality of service congestion control. Voice queues  203  and  208  do not implement this type of congestion control mechanism because voice cells must be delivered and received at a constant bit rate. Therefore, congestion control that varies the rate of voice cells below its minimum required transmission rate is unacceptable. 
     FIG. 2  illustrates a prior art scheme of data transmission implementing variable rate quality of service congestion control. As described in  FIG. 1 , telephone  201  transmits voice cells to switch  22  via bi-directional communication link  202  at a fixed data rate. Voice queue  203  accepts the voice cells and passes the voice cells onto cell selector  212 . Likewise, workstation  204  passes workstation cells to cell selector  212  via bi-directional communication links  202 , rate controller  205 , queue  206  and congestion control mechanism  210 . Cell selector  212  then transmits voice and workstation cells to another switch  22  via bi-directional communication channel  42 . Bi-directional communication channel  42  has a variable bandwidth (BW A )  218 . 
   If channel  42  has a fixed bandwidth, the sum of the voice cell rate (R 1 )  216  and workstation cells rate (R 2 )  217  would be equal to BW A    218 . R 1    216  would be equal the fixed bandwidth (BW F )  214  required by telephone  201 . R 2    217  would equal the variable bandwidth (BW V )  215  provided by rate controller  205 . Cell selector  212 ; therefore, would output cells at a rate equal to BW A    218  of channel  42 . 
   If BW A    218  does not decrease, BW F    214  (representing the fixed data rate required for voice communications) is equal to R 1    216  (representing the data rate at which cell selector  212  sends data to channel  42 ). Thus, voice queue  203  does not back-up. If the bandwidth of channel  42  increases, a similar result occurs. 
   However, if BW A    218  of channel  42  is decreased to a new lower value, then cell selector  212  can only output cells at a maximum rate of the lower BWA. To compensate, cell selector  212  accepts cells at a lower data rate by decreasing R 1    216  to a new lower value and by decreasing R 2    217  to a new lower value. The decreases in R 1    216  and R 2    217  are typically proportional to the decrease of BW A    218 . Rate controller  205  compensates for the decrease of R 2    217  so queue  206  experiences no congestion. However a decrease of BW A    218 , causes voice cells from telephone  201  to experience congestion at voice queue  203 . The cause of this congestion is apparent from the following example. 
   Suppose BW A    218  is 2,000 cells per second, BW V    215  is 1,000 cells per second and BW F    214  requires 1,000 cells per second to properly transmit voice cells. Neither voice queue  203  nor queue  206  suffer congestion and there is no data loss. Now suppose BW A    306  is reduced to 1,500 cells per second. Cell selector  212  is forced to output cells at a rate no greater than 1,500 cells per second. Therefore, cell selector  212  sets R 1    216  and R 2    217  to 750 cells per second. Queue  206  suffers no congestion since congestion control mechanism  210  and rate controller  205  reduce the data flowing into queue  206  to  750  cells per second. However, voice queue  203  suffers congestion and cell loss  213  because BW F    214  still requires a data rate of 1,000 cells per second, but R 1    216  is only 750 cells per second. Thus voice queue  203  is congested and backs-up causing  250  cells per second of lost cells  213  from voice queue  203 . The quality of service is very poor for voice since one quarter of the cells are lost. 
   SUMMARY OF THE INVENTION 
   A method for queuing control of variable bandwidth communications channels is disclosed. A change from a first bandwidth to a second bandwidth of a communication channel is detected. A quality of service controller is adjusted to compensate for the change from a first bandwidth to a second bandwidth. 
   Other features and advantages of the present invention will be apparent from the accompanying drawings and from the detailed description that follows below. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The present invention is illustrated by way of example, and not limitation, in the figures of the accompanying drawings in which like reference numerals refer to similar elements and in which: 
       FIG. 1  illustrates a prior art internal block diagram of a digital switch; 
       FIG. 2  illustrates a prior art scheme of data transmission; 
       FIG. 3  illustrates a communication scheme implementing dynamic queue control for variable throughput communication channels according to one embodiment of the present invention; and 
       FIG. 4  illustrates a flow diagram of processing logic carried out in one embodiment of the present invention. 
   

   DETAILED DESCRIPTION 
   Techniques for implementing dynamic queuing control are disclosed. As will be discussed in greater detail below, in one embodiment of the invention, by monitoring changes in the bandwidth of a communications channel between two network switches, a quality of service controller dynamically allocates and maintains fixed minimum transmission rates for high priority cell traffic. When a decrease in bandwidth of the channel occurs, high priority cells are allocated the fixed minimum transmission rate required to prevent the delay and loss of these high priority cells. 
   One advantage is to prevent the delay or loss of high priority cells, thus improving the quality of service of a communications network having a variable throughput communication channel. Another intended advantage is to improve the latency—i.e., reduce the congestion experienced at a queue—caused by a decrease in bandwidth of a variable throughput communication channel. 
     FIG. 3  illustrates a communication scheme implementing dynamic queue control for variable throughput communication channels. Although only described with respect to two data sources and paths—i.e., fixed bandwidth voice cells from telephone  307  and variable bandwidth workstation cells from workstation  314 —a great number of sources of different traffic classes may be used. For example, one source may be video, another source may be a mainframe, and another a satellite. 
   Typically, switches are capable of handling many different classes of cell traffic, each class having different characteristics and different service requirements. The various classes of cell traffic might include high priority traffic, voice, high speed deterministic traffic, bursty data, etc. For example, voice traffic is relatively delay sensitive and insensitive to occasional cell loss. In contrast, data traffic, such as file transfer, is relatively insensitive to delay but is data loss sensitive. High priority data is both delay and loss sensitive. To accommodate these differences, each class of traffic is typically placed in a preassigned queue, each with a different service priority. 
   Switch  405  includes a quality of service controller  400 . For one embodiment, controller  400  interfaces with the outputs of voice queue  309  and queue  310 . Controller  400  transmits cells to channel  313 . Although described with respect to T1 lines, the channel  313  could be any communication channel, including but not limited to a fiberoptic line and a magnetic carrier wave such as microwave or radio frequency communication links. Bi-directional communication channel  313  has a certain available variable bandwidth (BW A )  306 . BW A    306  could decrease for many reasons. For example, if channel  313  is a trunk of T1 lines and one T1 line fails or is broken, BW A    306  is decreased. In another example if channel  313  is a radio frequency link that is distorted in a lightning storm BW A    306  is decreased. 
   Controller  400  includes a rate controller for each data class. Thus, for voice cells from voice queue  309 , requiring a fixed transmission rate, controller  400  has voice rate controller  403 . And for workstation cells output from queue  310  requiring only a variable transmission rate, controller  400  has a workstation rate controller  402 . Both voice rate controller  403  and workstation rate controller  402  continuously provide cells to cell selector  404 . As will be discussed in greater detail below, cell selector  404  in turn transmits cells to another switch  405  via channel  313 . 
   Controller  400  includes processor  401  to control channel  313  and rate controllers  402  and  403 . For one embodiment, processor  401  is a MIPS™ 4650 processor sold by MIPS Technologies, Inc., 1225 Charleston Road, Mountain View, Calif. For alternative embodiments, processor  401  could be another type of processor. 
   The software implementing embodiments of the present invention can be stored in main memory  406  or any other storage medium accessible to processor  401 . This software may also be resident on an article of manufacture comprising a computer readable mass storage medium, or propagated digital signal having computer readable program code embodied therein and being readable by the mass storage device and for causing the processor  401  to perform digital information library transactions and protocols in accordance with the teachings herein. 
   Processor  401  calculates BW A    306 . Given BW A    306 , processor  401  calculates values of voice cell rate (R 1 )  304  and workstation cell rate (R 2 )  305  that prevent data loss and congestion in queues  309  and  310  respectively. Specifically, bandwidth is allocated from BW A    306  such that R 1    304  is set to equal fixed bandwidth (BW F )  302  required by telephone  307 . Thus, voice queue  309  experiences no congestion or latency (i.e., a back-up in the queue). R 2    305  is allocated the remaining bandwidth from BW A    306 . Therefore, there is no data loss and the quality of service requirements are met since the minimum data rate required by voice is maintained. From their respective queues, rate controllers  402  and  403  output cells to cell selector  404  at rates R 1    304  and R 2    305  respectively. 
   Selector  404  functions like a multiplexer. Selector  404  has multiple inputs for receiving cells from queues  309  and  310  and transmits a single stream of cells composed of cells from the various queues  309  and  310 . Queues  309  and  310  continuously provide cells for transmission to selector  404 . Selector  404  chooses cells from either queue  309  or  310  based upon their priority. A cell&#39;s priority is determined by the rate requirements of the source&#39;s class. For example, since voice cells require a fixed minimum bandwidth (BW F )  302  for transmission, voice cells from voice queue  309  are given a higher priority than workstation cells from queue  310 . In other words selector  404  may be programmed to transmit two voice cells from queue  309  for every workstation cell provided by queue  310 . Therefore, cell selector  404  outputs cells at a rate of the sum of R 1    304  and R 2    305 . The sum of R 1    304  and R 2    305  equals BW A    306 . In another embodiment, as described above, a multitude of sources having associated priorities provide cells to queues such that cell selector  404  is programmed to transmit cells into channel  313  based upon the multitude of sources&#39; priorities. 
   The following example further clarifies the queuing control of one embodiment of the present system. Referring to  FIG. 3 , suppose telephone  307  requires a fixed bandwidth (BW F )  302  data rate of 1,000 cells per second to maintain communications with other telephones in system  20 . Workstation  314  has a variable bandwidth (BW V )  303  controlled by congestion controller  311  and rate controller  315  of 1,000 cells per second. Under normal conditions BW A    306  is 2,000 cells per second and handles all data from telephone  307  and workstation  314 . Now suppose BW A    306  is reduced to 1,500 cells per second. Processor  401  detects this change in BW A    306  and adjusts R 1    304  to maintain the required voice rate of telephone  307  of 1,000 cells per second. Processor  401  calculates the remaining available bandwidth for workstation  314  as 500 cells per second and adjusts R 2    305  and cell selector  404  to transmit data from workstation  314  through channel  313  at a rate of 500 cells per second. Congestion controller  311  and rate controller  315  adjust BW V    303  such that queue  310  maintains its quality of service. During periods of network traffic congestion, when network traffic demand exceeds the network&#39;s bandwidth capacity, servicing algorithms are typically employed to discriminate between traffic classes in order to allocate bandwidth. Delay is managed by properly sizing the queue depths and prioritizing transmission within a class based upon a measure of the time that a cell has been in the network as, for example, by use of time stamps and hop counts. 
   Thus, no data is lost or excluded due to congestion at queues  309  or  310 . If processor  401  detects an increase in BW A    306 , then R 1    304  and R 2    305  are adjusted to allow the maximum data rate possible. If BW A    306  remains unchanged, then R 1    304  and R 2    305  also remain unchanged. 
   Data loss in queue  309  is prevented as follows.  FIG. 4  is a flow chart of the logic implemented by processor  401 . In decision block  501 , processor  401  determines if BW A    306  is the maximum possible bandwidth of channel  313 . In one embodiment, each line that is part of channel  313  is “pinged” to determine if it is still active. In other embodiments, other handshaking methods are used. If maximum BW A    306  is available, processor  401  continues to monitor the channel  313  for a change in bandwidth. If no, in processing block  502 , processor  401  calculates the available bandwidth of channel  313 . In processing block  503 , priority is assigned to each class of data as described above to ensure a constant data rate for sources requiring a minimum fixed data rate such as voice transmissions. In processing block  504 , the total available bandwidth  306  of channel  313  is allocated to data sources based upon the assigned priorities. For example, processor  401  may allocate two voice cells to be transmitted by selector  404  for every one workstation cell transmitted. Thus R 1    304  would equal two thirds BW A    306  and R 2    305  would equal one third BW A    306 . 
   Also in processing block  504 , data classes are calculated such that fixed data rate classes are allocated their minimum required bandwidth and variable data rate classes are allocated the remaining bandwidth. For example, if R 1    304  requires all of BW A    306  to maintain voice transmissions, processor  401  would set R 1    304  equal to BW A    306 . R 2    305  would be allocated any remaining bandwidth from BW A    306 . In processing block  505 , processor  401  provides rate controllers  402  and  403  the workstation and voice rate values respectively. In processing block  506 , processor  401  provides cell selector  404  priority information for selecting higher priority cells to guarantee a minimum bandwidth for fixed rate data sources such as voice as described above. Upon completion of block  506 , flow control is passed back to decision block  501  and the BW A    306  of channel  313  is continuously monitored. Thus processor logic ensures that no data type is excluded or lost due to congestion. 
   Thus, techniques for implementing dynamic queuing control have been disclosed that prevents the delay or loss of high priority cells. As a result a switch has an improved quality of service. Further advantages include improved latency since queues  309  and  310  have decreased congestion. 
   In the forgoing specification, the invention has been described with reference to specific exemplary embodiments thereof. If will, however, be evident that various modifications and changes may be made thereto without deporting from the broader spirit and scope of the invention as set forth in the appended claims. The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive manner.