1. Field of the Invention
This invention relates generally to data communications and the interface between a computer system and a network, and more particularly to methods and apparatuses for efficiently transmitting Asynchronous Transfer Mode (ATM) cells over an ATM network.
2. Description of the Related Art
ATM configured networks allow for high-speed data, voice and video communications to be conducted between endpoint computer systems. ATM networks, which are based on the transmission of fixed-length data packets, have proven to be extremely useful because they combine the benefits of both a switched network (e.g., constant transmission delay, guaranteed capacity) and a packet switched network (e.g., flexibility and efficiency for intermittent traffic).
Current ATM standards are defined by the International Telecommunication Union (ITU), and ATM Forum specifications, which are herein incorporated by reference. As is common in contemporary communications protocols, several protocol layers are used to functionally divide the communications task within an ATM network. The ATM protocol layers are similar in scope to the Open System Interconnection (OSI) reference model that is defined by the International Standardization Organization (ISO).
In ATM networks, a variable length PDU defines the data to be shared between higher protocol layers, such as the application layer software programs operating at the endpoint computer systems. A typical PDU includes the data to be shared along with additional header and trailer information. To transmit the PDU over an ATM configured network, each PDU is further divided into fixed-length transmission units, known as cells. A typical cell is 53 bytes long and includes a 5-byte header containing a connection identifier and a 48-byte payload. Thus, for example, a 480-byte PDU would be divided into ten cells, each cell having a 48 byte payload or one tenth of the PDU.
During transmission, a cell is sent from one endpoint computer system to another through a virtual circuit (VC) within the interconnecting ATM network. A VC typically consists of a concatenation of communication links established between the two endpoints where higher layer protocols are accessed. By definition, ATM cells are transmitted in a sequence over an established VC. As such, the VC must exist throughout the transmission of a PDU. One of the advantages of an ATM configured network is that a number of VCs can be established over a single wire or fiber connecting the sending computer system to the network by time-division multiplexing the cells from different PDUs.
Typically, an ATM Network Interface Card (NIC) and accompanying software are provided within the sending (or receiving) endpoint computer systems to transmit (or receive) the cells of a PDU over a VC. In terms of the OSI reference protocol model, a typical NIC provides link layer functionality by supplying cells in a specific sequence to the physical layer of the ATM network. In contrast, the VCs within the ATM network are typically established at a higher level layer, as are the PDUs and information therein.
FIG. 1a is a block diagram illustrating a typical ATM network having a first endpoint computer labeled host 12, a network 14, and one or more additional endpoint computers labeled end stations 16. Within network 14 there are illustrated, by way of dashed connecting lines, a plurality of virtual circuits 18 that represent the communication channels established between host 12 and end stations 16 during an ATM communication. By way of example, network 14 may include one or more telecommunications and/or data networks, having switching devices, routing devices, and dedicated communication lines and/or fibers that are capable of providing a communication link between host 12 and end stations 16. Host 12 and end stations 16 may, for example, be personal computer systems, workstations, mainframes, or other like processing devices that are capable of sending and receiving ATM PDUs.
FIG. 1b is a block diagram that illustrates one possible configuration of an endpoint computer system, such as host 12 in FIG. 1a, having a processor 20, a host bus 22, a system memory 24, a PCI controller 26, a PCI bus 28, a NIC 30, and an optional SCSI interface (I/F) 32 and SCSI device 34. Processor 20 can for example be a microprocessor or central processing unit (CPU) configured to access system memory 24. System memory 24 can for example be a dynamic random access memory (DRAM) that is accessed via host bus 22, or by way of another interconnecting circuit. SCSI device 34 can for example be a secondary data storage device, such as a disc drive unit, that can be accessed by processor 20 by way of host bus 22, PCI controller 26, PCI bus 28, and SCSI interface 32. As shown, processor 20 can also access network 14 by way of PCI bus 28 and NIC 30. It is recognized that additional processors and other devices and additional buses, etc., can be connected to either the host bus or PCI bus, as is common in modern computing configurations.
In a typical endpoint computer system, when the higher level protocol and/or application layers require a PDU to be transmitted over network 14 to another endpoint computer system several process steps typically occur. First, a VC is typically established by processor 20 via NIC 30. Next, the PDU is stored in system memory 24 by processor 20. Following that, NIC 30 is directed by processor 20 to complete the desired PDU transmission.
Thus, in order to complete the transmission of the PDU, in a typical configuration, NIC 30 needs to fetch the PDU data, segment it into cells, and transmit these cells, one-by-one, over a VC in network 14. As such, one important consideration in the design and operation of a NIC and associated software is the timing or scheduling of the cells for transmission over the network.
The ATM Traffic Management Specification, Version 4.0, available from the ATM forum and incorporated herein by reference for all purposes, specifies the types of traffic to be carried by an ATM network and various parameters associated with the transmission of cells over the network. For example, each VC can be assigned a traffic type based on the type of information being carried (e.g., video, voice or data), and/or the characteristics of the application using the VC. Currently, defined traffic types include Continuous Bit Rate (CBR), Variable Bit Rate (VBR), Available Bit Rate (ABR), and Unknown Bit Rate (UBR).
By way of example, a CBR VC or channel can include voice data which typically needs to be sent and received at a substantially constant rate. In this case, the NIC, for example, can transmit cells for the VC at a rate not to exceed a maximum transmission rate, known as the Peak Cell Rate (PCR), which is typically measured in cells per second. For a CBR channel the PCR is typically set when the VC is first established.
An example of a variable bit rate (VBR) channel is a VC carrying compressed video data. As its name implies, the allowed transmission rate for VBR channels varies with time according to a formula specified in the Traffic Management Specification and parameters that are negotiated when the VC is first established.
Data traffic is an example of the information that can be transmitted over an available bit rate ABR channel. Typically, ABR channels use any unused bandwidth available when other types of channels are not transmitting. Typically a feedback mechanism from the network is used to indicate when bandwidth is available.
Alternatively, data traffic can also be transmitted over a unknown bit rate UBR channel. Basically, when a VC is first established as a UBR channel, no bandwidth over the network is reserved for the channel. As a result, the NIC, for example, can transmit UBR cells up to a maximum PCR. Upon receiving these cells, the network will typically either accept them or reject them. Rejected cells, which are essentially dropped by the network, will therefore need to be re-transmitted. Re-transmission is typically accomplished through the higher level software layers.
Thus, schedulers need to have the capability to handle both static (e.g., CBR) and dynamic transmission rates (e.g., VBR & ABR). Additionally, schedulers must also have the capability to handle different priorities for each of the VCs. Typically, CBR channels are the highest priority followed by VBR, ABR, and then UBR channels. Further, to be considered ATM compliant, schedulers are usually required to ensure that cells are not transmitted too soon. As a result of these and other considerations, such as circuit complexity, cost, etc., conventional schedulers have not always provided optimal use of the ATM connection leading to the network, and/or the internal devices within the computer system.
By way of example, conventional schedulers can basically be grouped into one of three types depending on the internal scheduling method employed. The first type maintains a separate on-chip counter for each VC. Each of these counters is decremented a preprogrammed amount each cell transmission cycle, or some other timing event occurs. When the counter for a given VC reaches a particular value, the VC is eligible to have a cell transmitted. Since two VCs may have their respective counters reach the defined value at the same time, a arbitration mechanism is typically used to decide which VC is entitled to transmit first. An example of this type of a "counter per VC" scheduler is provided with the Orion and Gemini SAR chips (Models AIC-5900, AIC-5905, respectively) available from Adaptec, Inc. of Milpitas, Calif. One drawback to this type of scheduler is that there needs to be a separate counter for each VC. Thus, for large numbers of VCs, for example 1,000, there would need to be 1000 separate counters. As can be appreciated, this may not always be feasible.
The second type, which is similar to the first type, includes a counter for each of a number of defined transmission rates. Each VC is therefore assigned to one of the transmission rate/counters. When, for a given transmission rate, the counter reaches a particular value, a cell can be transmitted from each of the VCs assigned to the given transmission rate. Again this requires that an arbitration mechanism be provided to determine the exact ordering of the cells during transmission. An example of this type of a "counter per rate" scheduler is provided in the Fujitsu MB86687A chip documentation available from Fujitsu Microelectronics, Inc., San Jose, Calif.
While this second type of scheduler can support many VCs, there is a finite number of rates at which the VCs' cells can be transmitted. Unfortunately, this can decrease the efficiency of the ATM network and/or the computer systems attached thereto. Furthermore, implementing this type of scheduler to support dynamically changing transmission rates can be difficult, since several VCs may be assigned to share a given rate/counter. On the other hand, if a counter is dedicated for use by a single dynamic channel (e.g., VBR, or ABR) then the number of VCs that may be supported by the scheduler tends to decrease. This is especially true if several counters are each dedicated to specific dynamically changing VCs.
The third type of scheduler requires that a pre-scheduled list be created to specify the times at which the various cells associated with a multiplicity of VCs are to be sent. This is typically accomplished by way of a software algorithm running on a processor located in a host computer system. The pre-scheduled list is then provided to the NIC. An example of this type of a "pre-scheduled list" scheduler is provided in the Integrated Device Technology IDT77201 chip documentation available from Integrated Device Technology Inc., of Santa Clara, Calif.
The third type of scheduler can typically handle large numbers of VCs wherein each of the VCs can have a unique rate. Unfortunately, because this type of scheduler requires that the schedule be created in advance of the start of the first cell transmission time, it can not therefore be quickly modified to account for dynamically changing rates in one or more of the VCs.
Thus, what is desired are improved scheduling methods and apparatuses that more effectively multiplex cells from a plurality of VCs, allow each VC to have a unique transmission rate that can be dynamically adjusted, and can support a plurality of transmission priority levels.
USPTO Backgrounds
USPTO Backgrounds