Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
2000-06-13
2002-02-19
Rao, Seema S. (Department: 2661)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S235100, C370S412000, C370S395400
Reexamination Certificate
active
06349089
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to communication networks, and more specifically to a method and apparatus for scheduling cells in queues for transmission in an asynchronous transfer mode (ATM) switch.
2. Related Art
Different types of communication networks have evolved in the past to provide different types of services. For example, voice networks allow users to converse in a telephone conversation and data networks allow users to share vast quantities of data. In general, each type of communication network can have different requirements for providing the corresponding services. As an illustration, voice networks may need predictable bandwidth with low latencies to support voice calls while data networks may need high bandwidth in bursts to support large data transfers.
Due to such varying requirements, different types of communication networks have evolved with separate communication backbones, possibly implemented with different technologies. Often, these different technologies are implemented using very different techniques or principles. For example, voice networks have been implemented using a technique commonly referred to as time division multiplexing, which provides fixed and predictable bandwidth for each voice channel. On the other hand, data networks (such as those based on Internet Protocol) have been implemented to share available bandwidth on demand. That is, any end-system of a data network can potentially use all the available bandwidth at a given instance of time, and then the other systems have all the bandwidth for use.
In general, having separate communication backbones for communication networks results in inefficiency in the usage of the overall bandwidth. According to the well-known principle of ‘economy of scale’, ten servers serving hundred customers of a single queue generally provide slower service than thousand servers serving ten thousand clients even though the server-client ratio is the same. There is more efficiency with larger numbers typically because any of the larger pool of available servers can immediately serve a customer in a queue, and thus keep the queue length short.
The inefficiency (due to separate communication backbones) can result in degradation of aggregate service levels or in inability to provide more services. The problem can be exasperated with the increasing demands being placed on the networks. In addition, the overhead to manage the separate networks may be unacceptably high due to the increased number of components in the overall system. Further, the same end-station can be providing different services, which have varying requirements. For example, a computer system may be used for diverse applications such as data sharing, telephone conversations, and video conferencing applications.
Accordingly, the communications industry has been migrating towards a shared communications backbone for all the different types of services. Asynchronous transfer mode (ATM) is one standard which allows such a shared communication backbone. In general, an ATM network includes several ATM switches connecting several end-systems. Each switch includes several ports to connect to end systems and other switches. A switch receives a cell on one port and forwards the cell on another port to provide a connection between (or among) the end-systems.
To communicate with another end-system, an end-station of a communication network usually ‘opens a connection’. Opening a connection generally refers to determining a sequence of switches between the two end-stations such that the switches provide at least one communication path between the two end-stations with any specific service levels required for the communication. Once a connection is established, the end systems communicate with each other using cells in an ATM environment. The switches in the communication path receive cells on one port and forward the received cells on another port to support the connection.
Switches often maintain internal queues while transferring cells from one port to the other. The cells are buffered in the queues awaiting their turn for transmission. A scheduler determines the order of transmission of the queued cells according to a scheduling scheme. In one scheduling scheme, a queue is maintained for each connection, which provides the flexibility to serve each connection according to the specific service parameters (known as quality of service ‘QoS’ parameters) with which the connection may have been setup. The scheduler needs to schedule cells for transmission to meet these service requirements.
One such service requirement is fair scheduling. Fairness generally refers to proportional allocation of bandwidth to individual connections consistent with the QoS parameters associated with each connection. The QoS parameters can include, among others, a desired bandwidth and a priority for each connection. For example, assuming equal priority, cells belonging to a higher bandwidth connection may need to be transmitted more often than cells belonging to lower bandwidth connections independent of the order in which the cells of the connections may have arrived into the switch or at the output port during internal processing in the switch.
Another service requirement is ‘shaping’. Shaping refers to the provision of a specified maximum bandwidth (“shaping rate”) to a connection. Shaping provides the ability to restrict a connection from using more bandwidth than the shaping rate. Such restriction provides a network manager the ability to establish cost structures commensurate with the bandwidth a connection can use. In addition, shaping can prevent switches or end-systems down the connection path from being over-flooded with cells from the connection.
A scheduler may need to schedule cells of a connection while restricting the maximum bandwidth used by the connection to the shaping rate. The scheduling function may need to be performed without consuming undue amounts of memory space or processing power to avoid throughput performance bottlenecks in the switch. Therefore, what is needed is a scheduler which can shape a connection without requiring excessive memory or processing power.
In addition, a scheduler may need to support dynamic change of shaping rate. For example, if the ATM backbone is lightly congested, it may be desirable to increase the shaping rate of a connection. The level of congestion can be determined, for example, based on available bit rate (ABR) ATM service, which is communicated to other switches in a connection path.
Another feature which may enhance the acceptance of ATM technology is efficient support for transmission of frames. Frames typically refer to data packets sent by end-systems such as those in the Internet Protocol environment. A frame is usually broken into small cells suitable for transmission on ATM communications backbones, and reassembled before being delivered to the end-system. Accordingly, what is also needed is a scheduler which supports the efficient transmission of frames in an ATM backbone.
Yet another requirement may be that all the above service requirements and features may need to be supported in one integrated framework so that a switch can be designed to provide all the features. The framework needs to take into consideration what may appear as contradictory requirements. For example, when scheduling cells of a non-shaped connection, it is generally acceptable (and many times desirable) to provide more bandwidth than which is desired for the non-shaped connection. In contrast, the shaped connections need to be restricted from using more bandwidth than the shaping rate.
Therefore, what is also needed is an integrated framework which enables the provision of any of the desired features and services noted above as requested on a per-connection basis.
SUMMARY OF THE INVENTION
The present invention is directed to a flexible scheduler in a cell switch. The scheduler enables the cells of various connections to be scheduled fairly while providing for efficient shaping
Bonomi Flavio Giovanni
Devarajan Kannan
Rao Seema S.
Riverstone Networks, Inc.
Thappeta Naren
LandOfFree
Flexible scheduler in an asynchronous transfer mode (ATM)... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Flexible scheduler in an asynchronous transfer mode (ATM)..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Flexible scheduler in an asynchronous transfer mode (ATM)... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2939502