US 6233245 Method and apparatus for management of bandwidth in a data communication network
ABSTRACT – The present invention relates to the field of data communication networks. More specifically, it pertains to devices and methods for the management of bandwidth on links between routing nodes in data networks. The system is particularly useful for reducing congestion caused by high volume traffic streams. The invention provides a novel router that separates traffic on the basis of data type into separate queues buffers. The various queue buffers are associated with virtual output ports on a common physical link. A scheduler regulates the data release from the queue buffers into the physical link to control the bandwidth portion that is made available to each type of data.
FIELD OF THE INVENTION
The present invention relates to the field of data communication networks. More specifically, it pertains to devices and methods for the management of bandwidth on links between routing nodes in data networks. The system is particularly useful for reducing congestion caused by high volume traffic streams.
BACKGROUND OF THE INVENTION
A typical data communications network operates in a connectionless mode whereby there is no negotiation between the transmitter/receiver and the network with regard to the type or quantity of traffic that is to be sent. The transmitter simply sends the traffic on the network, and relies on the network components to deliver that traffic to the receiver accurately. In these networks, the protocols used by the transmitters and receivers are designed to accommodate the delay and loss that can arise from congestion. These same protocols also adapt the traffic flow to some extent to help alleviate congestion.
The networks are typically made up of routing nodes (routers) joined by physical links. The main function of the routing nodes is to direct incoming packets to the appropriate outgoing links. Congestion in the routing nodes is usually caused by an amount of traffic directed to a physical link exceeding its capacity. Queues form in the routing nodes and, when the queue (buffer) overflows, packets are lost. These buffers can smooth out transient surges of traffic, but ultimately, packets are discarded. For the Transmission Control Protocol (TCP from the Internet TCP/IP protocol suite), the loss of packets is a stimulus to reduce the rate of transmission and help share the link bandwidth in a controlled way. Other protocols, such as UDP (Unacknowledged Datagram Protocol), do not adapt in this way, and an application using UDP to transfer information can continue to send traffic regardless of congestion on the links.
High volume traffic streams on the network accelerate congestion and, if they cannot adapt to alleviate that congestion, can seriously impact the performance for all other network users. Streaming video is an example of such high volume traffic. Video is becoming more and more prevalent and it is anticipated that the presence of video sources may cause severe problems for TCP users.
One solution to this problem is to replace the routed (connectionless) network by a connection-oriented network such as an ATM network that allows for traffic segregation and bandwidth allocation. Unfortunately, this solution is undesirable because of capital costs, retraining and the requirement for new network management procedures.
Another solution is provided by the fact that the Internet Engineering Task Force (IETF) is defining new protocols for bandwidth management and newer high-end routers will have the capability of implementing bandwidth management. However, this solution requires new hardware or software and is not yet widely available. Furthermore, many network providers will find that replacing existing equipment is too expensive.
The background information presented herein clearly shows that there exists a need in the industry to provide a method for simple management of bandwidth in a data communication network particularly well suited for reducing congestion caused by high volume traffic streams.
SUMMARY OF THE INVENTION
An object of this invention is to provide a system capable of implementing a bandwidth control mechanism on a physical link connecting the router to another node of the network.
Another object of the invention is to provide a method for controlling bandwidth in a connection-less network.
As embodied and broadly described herein, the invention provides a system for controlling the transmission of data traffic units into a physical link, each data traffic unit having a recognizable characteristic, said system comprising:
a first and second queue buffers capable of receiving data traffic units;
means for dispatching data traffic units from an incoming data stream to a selected one of said queue buffers on a basis of the recognizable characteristic of each traffic unit;
a scheduler for releasing data into the physical link from each of said first and second queue buffers at a certain rate.
In a preferred embodiment, the invention provides a novel router that implements a bandwidth control functionality on a certain physical link to which the router is connected. The router receives from an input port data traffic units, such as IP data packets to be transmitted to a certain output port, the choice of the output port being made by invoking the routing logic of the router. The routing decision is taken by reading a routing table that determines the best way for a packet to reach its destination. For instance, the address field in an IP data packet indicates the destination of the data packet. The router reads the address information and consults the routing table to determine the output port of the router through which the data packet should be sent so the desired destination is reached. This mode of data transfer is referred to as “connection-less” because there is no defined end-to-end connection in the network established during a certain data exchange transaction.
The router in accordance with the invention features a multiple queue structure associated to the physical link over which the bandwidth control is to be implemented. IP data packets arriving at an input port of the router and directed to the output port connected to the bandwidth controlled physical link are placed in a selected one of the queues. The choice of the queue that is to receive the data packet may be made on the basis of a certain recognisable characteristic of the IP data packet, such as the source address information from which one may derive the type of data that the packet contains. In a very specific embodiment, the router is provided with two separate queues, one queue being dedicated for video/voice data that consumer significant amounts of bandwidth, the other queue being reserved for the rest of the traffic that is transported over the bandwidth controlled physical link. That traffic may be file transfer, text transfer among many other types of data exchange that in general require much less bandwidth than video or voice traffic.
A scheduler mechanism controls the rate at which data is taken from one queue and passed to the physical link for transport to a desired destination. The scheduler mechanism effectively controls the bandwidth allocation for each type of traffic by gating the data from each queue to the physical link.
The separation of traffic in different queues limits the likelihood of high bandwidth data transmission interfering with the transmission of other traffic. In the case of video/voice data, the data packets are placed in the same queue and compete for bandwidth among themselves. The other traffic is protected from congestion by the video/voice data since it is placed in a different queue.
A convenient way to implement the functionality of the above described bandwidth control mechanism is to provide the router with an ATM interface that is designed to provide a multitude of virtual pathways within a single physical link. More specifically, it suffices to associate each queue with a certain virtual port on the ATM interface and transfer data from that queue to this reserved port. The ATM interface provides the scheduler mechanism functionality so the transfer of data on each virtual pathway is gated as desired. When data packets are passed to the ATM interface they are translated into an ATM format that is different from the IP data packet format normally used in the connection-less type data networks. For compatibility, the output end of the physical link should also terminate on an ATM interface to enable suitable re-translation to an IP data packet format.
Distinguishing the nature of the data in the data packets arriving at the input port of the router in order to determine in which queue the packet will be transferred may be difficult to achieve in practice. One theoretical possibility is to examine the payload or user data segment of the TP data packet in an attempt to determine the kind of data that is being transported. A simpler approach is to rely on the source address placed in the TP data packet, with prior knowledge of the kind of data this source is likely to be sending. For instance, some well identified sources may be sending mostly video or voice data. Any data packet issued from any one of those sources may then be assumed to contain video data and it will be transferred to the associated queue. Yet another possibility is to rely on the identity of the input port of the router at which the data packet has arrived. This is particularly suitable when the router has an input port connected to a single source that generates most of the time a certain data type, thus there is a strong likelihood that a data packet arriving at the designated port will be of the particular data type.
As embodied and broadly described herein, the invention provides a method for controlling the transmission of data traffic units into a physical link, each data traffic unit having a recognizable characteristic, said method comprising the steps of:
providing first and second queue buffers capable of receiving data traffic units;
dispatching data traffic units from an incoming data stream to a selected one of said queue buffers on a basis of the recognizable characteristic of each traffic unit;
releasing data into the physical link from each of said first and second queue buffers at a certain rate.
As embodied and broadly described herein the invention provides a router comprising:
a plurality of ports capable of supporting respective physical links, each port being capable of exchanging data traffic units with a respective physical link, each data traffic unit having a recognizable characteristic;
a first and second queue buffers capable of receiving data traffic units, said queue buffers being associated with a certain physical link:
means for dispatching data traffic units received through either one port and a plurality of ports by said router to a selected one of said queue buffers on a basis of the recognizable characteristic of each traffic unit;
a scheduler for releasing data toward the certain physical link from each of said first and second queue buffers at certain rate.