Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1997-12-18
2001-03-20
Vincent, David R. (Department: 2732)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S395430
Reexamination Certificate
active
06205151
ABSTRACT:
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
Not applicable.
BACKGROUND OF THE INVENTION
This invention is in the field of data communications, and is more specifically directed to asynchronous transfer mode (ATM) data communication.
In the field of digital communications, whether applied to voice, video, or data communication, various communication techniques have been developed for routing messages among nodes, or processors, that are connected over a network. One such approach is referred to as packet switching, in which certain network nodes operate as concentrators to receive portions of messages, referred to as packets, from the sending units. These packets may be stored at the concentrator, and are then routed to a destination concentrator to which the receiving unit indicated by the packet address is coupled. The size of the packet refers to the maximum upper limit of information which can be communicated between concentrators (i.e., between the store and forward nodes), and is typically a portion of a message or file. Each packet includes header information relating to the source network address and destination network address, which permits proper routing of the message packet. Packet switching ensures that routing paths are not unduly dominated by long individual messages, and thus reduces transmission delay in the store-and-forward nodes. Fast packet switching refers to packet switching techniques that operate at high data rates, up to and exceeding hundreds of megabits per second.
A well-known example of a fast packet switching protocol, which combines the efficiency of packet switching with the predictability of circuit switching, is Asynchronous Transfer Mode (generally referred to as “ATM”), in which packet lengths and organization are fixed, regardless of message length or data type (i.e., voice, data, or video). The fixed packets according to the ATM protocol are referred to as “cells”, and each ATM cell is composed of fifty-three bytes, five of which are dedicated to the header and the remaining forty-eight of which serve as the payload. According to this protocol, larger packets are made up of a number of fixed-length ATM cells. The fixed-size cell format enables ATM cell switching to be implemented in hardware, as opposed to software, resulting in transmission speeds in the gigabits-per-second range. In addition, the switching of cells rather than packets permits scalable user access to the network, from a few Mbps to several Gbps, as appropriate to the application. The asynchronous nature of the transmission permits ATM cells to be used in transmitting delay-tolerant data traffic intermixed with time-sensitive traffic like voice and video over the same backbone facility. To more efficiently utilize the bandwidth for these various applications, traffic management techniques are now employed which give priority to time-sensitive traffic relative to delay-tolerant traffic.
Recently, closed loop traffic management schemes have been developed for use in ATM data communication. Closed loop traffic management involves the use of feedback signals between two network nodes to govern the data rates of channels, with a goal of improving the efficiency of bandwidth utilization. This efficiency improvement is particularly necessary when communication of real-time voice and video information is involved, as the time-criticality of these channels can be disturbed by the transmission of large bursts of non-time-critical data.
Current traffic management schemes utilize various transmission categories to assign bandwidth in ATM communications. One high priority category is Constant Bit Rate (CBR), in which the transmission is carried out at a constant rate. Two categories of Variable Bit Rate (VBR) transmission are also provided, one for real-time data and another for non-real-time data. A low priority category is Unscheduled Bit Rate (UBR), in which data is transmitted by the source with no guarantee of transmission speed.
A relatively recent traffic management category is referred to as Available Bit Rate (ABR). In this category, feedback from the receiving network node, via Resource Management (RM) cells or by way of explicit flow control indications in data cells, is used by the source network node to dynamically control its transmission rate in response to current network conditions. This control is effected within certain transmission parameters that are specified upon opening of the transmission channel. Typically, the source and destination nodes agree upon the Peak Cell Rate (PCR) and Minimum Cell Rate (MCR), setting the upper and lower bounds of transmission for an ABR communication. Once these bounds are established, a flow control algorithm is executed, typically at the destination network node, to define the desired transmission rate for each channel. As is known in the art, thousands of connections may be simultaneously open between a given pair of network nodes. As such, traffic management can be a relatively complex operation, especially in controlling ABR category communications.
At the source network node, Segmentation and Reassembly (SAR) devices or operations are used to arrange and transmit ATM cells according to the desired bit rate established by the flow control algorithm. Conventional SAR devices often include “traffic shaper” functions, often known as “leaky buckets”, as they include buffers that can rapidly fill up with cell data during bursts, but steadily “leak” or transmit data over the network. The complexity of scheduling transmission from these buffers increases dramatically with the number of channels being handled, and particularly when ABR communications are involved.
As an alternative to the leaky bucket approach, some conventional source node SAR devices are implemented by way of high-performance microprocessors, programmed to handle the scheduling of ATM cells among many channels. However, the use of such microprocessors, typically implemented as a RISC coprocessor, can be quite substantial, especially when considering the substantial amount of external memory that is required for storing programs, caching transmission data, and for providing bus interface functions. For example, the provision of a buffer for storing a number of transmission cells for each of 2048 channels, along with a counter dedicated to each channel that counts the number of cycles since the last transmission for that channel (used to determine when the next cell may be transmitted), requires a very large memory resource for this function.
BRIEF SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide an efficient scheduling function for Available Bit Rate (ABR) Asynchronous Transfer Mode (ATM) transmissions.
It is a further object of the present invention to provide such a scheduling function that can be implemented with modest memory requirements.
Other objects and advantages of the present invention will be apparent to those of ordinary skill in the art having reference to the following specification together with its drawings.
The present invention may be implemented into a translation system for communicating messages from a Local Area Network (LAN) to ATM transmissions. The translation system includes a Segmentation and Reassembly (SAR) function that operates in combination with an ABR scheduling function. The ABR scheduler includes circuitry for maintaining a heap data structure, in which each entry includes a channel identifier associated with a timestamp. The timestamp is a timer value that indicates the next time at which a cell for the associated channel is to be transmitted. A heap sort process is executed so that a root element in the heap data structure corresponds to the next cell to be scheduled for transmission. According to one aspect of the present invention, the heap data structure may be stored in an on-chip memory resource and external memory, where the most recent heap sort results are stored on-chip.
REFERENCES:
patent: 5796735 (1998-08-01), Miller et al.
patent: 5812527 (1998-09-01), Klin
Karguth Brian J.
Prasad Sharat
Quay Jeffrey R.
Brady III Wade James
Telecky , Jr. Frederick J.
Texas Instruments Incorporated
Vincent David R.
LandOfFree
ATM cell scheduler which uses a heap memory and associates... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with ATM cell scheduler which uses a heap memory and associates..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and ATM cell scheduler which uses a heap memory and associates... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2499422