Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-09-09
2003-09-09
Marcelo, Melvin (Department: 2663)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S412000, C370S465000
Reexamination Certificate
active
06618380
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to a method and apparatus for managing queued data and, in particular, for prioritizing data packets flowing through equipment in packet switched networks to provide specific bandwidths to customers.
BACKGROUND OF THE INVENTION
Frame Relay networks have proven to provide a successful wide area networking service as evidenced by the exponential increase in the market of Frame Relay services and access devices. Frame Relay network service is provided by most carriers, Regional Bell Operating Companies (RBOCs), and some non-traditional service providers like Compuserve. Asynchronous Transfer Mode (ATM) switching networks, on the other hand, are gaining momentum in the industry and ATM networks are likely to become the preferred backbone networking technology in the future because of its ability to support a wide variety of network services.
It is envisioned that Frame Relay networks and ATM networks and services will coexist and be inter-connected by Inter-Working Units (IWUs) for some time until ATM networks becomes a more mature, stable, cost-effective technology. These IWUs accomplish the frame/packet format translations between Frame Relay networks and ATM networks. Frame Relay networks will continue to provide effective services for OC-3 or lower access speeds. In addition, it is unlikely that the Frame Relay network service users will forego their investments in Frame Relay network equipment in favor of ATM network service and equipment.
In networks there are typically a large number of defined channels over which data packets are carried. Each channel shares the resources of the network. Typically, a minimum bandwidth is assigned to each channel in the network according to a contract between the network provider and an entity to which a channel is assigned.
Network resources of the type in which a minimum bandwidth is contracted for by each channel have suffered from a variety of problems in their allocation of bandwidth to the active channels at a resource, i.e., those channels at the resource that are carrying data elements at a particular time. Resource scheduling is required whenever there is a contention for network resources among contending “flows”. The prior art teaches some solutions to resource scheduling such as round-robin scheduling and polling scheduling, but each of these solutions are generally constrained in their ability to adapt to different types of operation.
One such problem is how to assign available bandwidth for network resources among active channels. Another problem relates to insuring that the active channels are allowed to actually make use of all of the bandwidth for which they have contracted. This problem arises because it is possible that an end-to-end protocol being employed over a channel may interact with congestion control mechanisms employed by the network in such a way that a channel's contracted-for bandwith is never actually achieved.
Additional problems arise in the area of congestion control. Prior art congestion control techniques tended, in the face of congestion, to drop data packets from channels that exceeded their contracted-for bandwith. This, however, could exacerbate the congestion by causing such channels to restransmit their dropped data packets. Furthermore, such techniques for data packet dropping typically result in the retransmission over a channel of more data packets than were actually dropped. Another problem with prior art congestion control techniques is that many of them result in high delays for data packets in those channels that are transmitting within their contracted-for bandwidth. Lastly, errors that occur in the estimation of the actual bandwidth being used by each channel may cause a particular channel's data packets to be dropped even though such a channel is actually within its contracted-for bandwidth. This unnecessary data packet dropping results in additional data packet retransmissions and, potentially, additional congestion.
Another source for problems in the area of congestion control area has been in the Inter-Working Units (IWUs) which typically have not had resource scheduling to help provide contracted bandwidth. These tended to negate resource scheduling introduced elsewhere in the networks.
Thus, there is a need in prior art IWUs for priority queuing of data packets as they pass through to assure that individual channels receive and are allowed to actually make use of the bandwidth for which they have contracted.
SUMMARY OF THE INVENTION
The foregoing need in the prior art is satisfied by the present invention. A priority queuing arrangement in the transmit direction of Inter-Working Units (IWUs) is provided that permits Frame Relay data packets or ATM cells from channels that have contracted for a particular level of bandwidth service to be provided for that service, even during heavy traffic periods when there is contention for resources in the IWU.
REFERENCES:
patent: 5231633 (1993-07-01), Hluchyj et al.
patent: 5949789 (1999-09-01), Davis et al.
patent: 6169748 (2001-01-01), Barbas et al.
patent: 6262986 (2001-07-01), Oba et al.
patent: 6470016 (2002-10-01), Kalkunte et al.
Briem et al. “Traffic Managemetn for an ATM Switch with Per-VC Queuing: Concept and Implementation”. IEEE Communications Magazine. Sep. 21-26, 1997. pp. 88-93.*
Matsufuru et al. “Efficent Fair Queuing for ATM Networks using Uniform Round Robin”. IEEE Infocomm 1999. Mar. 21-25, 1999. pp. 389-397.*
Shimoshishi et al. “An Improvement of Weighted Round Robin Cell Scheduling in ATM Networks”. IEEE Global Telecommunications Conference. Nov. 3-8, 1997. pp. 1119-1123.*
Bennett et al. “High Speed, Scalabe and Accurate Implementation of Packet Fair Queueing Algorithms in ATM Networks”. IEEE Network Protocols. Oct. 28-31, 1997. pp. 7-14.
Kodialam Muralidharan Sampath
Mehta Vineet
Mueller Martin Ernst
Wang Yung-Terng
Ferris Derrick W
Lucent Technologies - Inc.
Marcelo Melvin
LandOfFree
Priority queueing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Priority queueing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Priority queueing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3000900