Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-03-27
2001-06-12
Ngo, Ricky (Department: 2664)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S412000, C370S429000
Reexamination Certificate
active
06246687
ABSTRACT:
BACKGROUND OF THE INVENTION
While Asynchronous Transfer Mode (ATM) was originally conceived as a carrier of integrated traffic, recent momentum for the rapid standardization of the technology has come from data networking applications. Since most data applications cannot predict their own bandwidth requirements, they usually require a service that allows all competing active virtual connections (VCs) to dynamically share the available bandwidth. The unspecified bit rate (UBR) and the available bit rate (ABR) service classes in ATM have been developed specifically to support data applications.
The UBR service is designed for those data applications that want to use any available bandwidth and are not sensitive to cell loss or delay. Such connections are not rejected on the basis of bandwidth shortage and are not policed for their usage behavior. During congestion, cells may be lost but the sources are not expected to reduce their cell rates. Instead, these applications may have their own higher-level loss recovery and retransmission mechanisms, such as the window flow control employed by transmission control protocol (TCP). The advantage of using UBR service for data transport is its simplicity and a minimal interaction required between users and the ATM network.
The ABR service has been developed with the goal of minimizing switch buffer requirements and cell loss in transporting data, and allowing users to have fair access to the available bandwidth. To achieve such service requirements, the ABR service uses congestion control at the ATM layer. It requires network switches to constantly monitor the traffic load and feed the information back to the sources. The sources are expected to adjust their input to the network dynamically based on the congestion status of the network. Thus, the benefits of ABR over UBR come at the expense of increased complexity in switches and end systems. Moreover, ABR also requires a certain level of interoperability among network switches.
In fact, there has been a continuing debate in the networking community about the need for ABR service. A major argument against ABR is that while ABR assumes that the end systems comply with the ABR source behavior, most current applications are only connected to ATM via legacy networks such as Ethernet. Therefore, ABR may only push congestion to the ATM network edges and cannot provide flow control on an end-to-end basis.
Furthermore, most users today are typically either not able to specify the range of traffic parameters needed to request most ATM services, or are not equipped to comply with the source behavior rules required by existing ATM services. As a result, there are many existing users for whom the benefits of ATM service guarantees remain unattainable. Those users access ATM networks mostly through UBR connections, which provide no service guarantees. In view of this, R. Guerin and J. Heinanen, “UBR+ Serve Category Definition”, ATM Forum Contribution 96-1598, December 1996, have proposed a new service, is originally named UBR+ but now called Generic Frame Rate or GFR, which will provide users with some level of service guarantees yet require minimal interaction between users and ATM networks.
The GFR service specifies that a user should be provided with a minimum service rate guarantee and with fair access to any excess available bandwidth. In other words, the GFR service will guarantee to a user a minimum throughput when the network is congested, while allowing a user to send at a higher rate when additional bandwidth is available.
U.S. Pat. No. 4,769,810 (“Packet Switching System Arranged for Congestion Control Through Bandwidth Management”) and U.S. Pat. No. 4,769,811 (“Packet Switching System Arranged for Congestion Control”), both to Eckberg, Jr., et al., describe several algorithms which attempt to provide comparable service by “marking” certain packets.
Upon arrival of a packet at a network boundary, a counter corresponding to a virtual connection is incremented by the number of bytes in the packet plus a fixed amount k. The counter is decremented by another fixed amount c at regular time intervals. If the counter exceeds some moving threshold, the packet is marked for possible discard at some other node, although marked packets are not necessarily discarded. If a node becomes congested, marked packets are dropped by the node.
SUMMARY OF THE INVENTION
In accordance with the present invention, guaranteed data rates are served in a cell switching network without the need for monitoring data rates or marking packets. To buffer cells in a switch, guaranteed buffer space per time interval T is assigned to individual virtual connections (VCs). In each of successive periods of time, the individual VCs are allocated available buffer space up to their guaranteed buffer space. After the connections are served their guaranteed buffer space, and within the remaining time of each period, excess buffer space is allocated to individual VCs.
In a preferred embodiment, cells are stored in at least one first-in-first-out (FIFO) buffer which serves plural virtual connections. For each incoming cell stored in the buffer, a corresponding virtual connection is identified and a cell count for that virtual connection is incremented. For each outgoing cell, a virtual connection cell count is decremented independent of the actual virtual connection with which the outgoing cell is associated.
Preferably, in each time period, each cell count is decremented first by a weight related to the associated guaranteed buffer space of the virtual connection and then according to a fairness algorithm, which in one embodiment decrements cell counts on a round robin basis.
In a preferred embodiment, when the buffer is filled to a fill threshold, and a cell count for some virtual connection is above a connection threshold, incoming cells associated with the virtual connection are blocked from storage in the buffer.
Individual virtual connection cell counts can be decremented to negative values. By allowing negative values, more data can be accepted for a virtual connection which has not been accessed for some time. This allows the VC to make up some bandwidth later for an earlier period of non-use. The cell counts have associated negative limits beyond which the cell counts cannot be decremented.
In an alternate embodiment, cells are buffered in queues where there is one queue per virtual connection, and buffer space is allocated by transferring data from a queue in order to free buffer space in the queue.
For optimal results, the techniques of the present invention are applied at every switch throughout the network. However, improved performance over the prior art is still obtained even where the present invention is not implemented in each switch.
REFERENCES:
patent: 5392280 (1995-02-01), Zheng
patent: 5664116 (1997-09-01), Gaytan et al.
patent: 5748629 (1998-05-01), Caldara et al.
patent: 5787086 (1998-07-01), McClure et al.
patent: 5867663 (1999-02-01), McClure et al.
patent: 6034945 (2000-03-01), Hughes et al.
Hamilton Brook Smith & Reynolds P.C.
Massachusetts Institute of Technology
Ngo Ricky
LandOfFree
Network switching system supporting guaranteed data rates does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Network switching system supporting guaranteed data rates, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Network switching system supporting guaranteed data rates will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2446959