Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-10-13
2003-02-25
Patel, Ajit (Department: 2732)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S230000, C370S412000
Reexamination Certificate
active
06526062
ABSTRACT:
BACKGROUND OF THE INVENTION
A. Field of the Invention
The present invention relates generally to systems for transmitting information over the Internet, and more particularly to scheduling the transmission of different types of traffic over the Internet.
B. Description of the Related Art
With the advent of highly-sophisticated digital audio and video applications run on modern multimedia workstations, the ability to run these applications over the Internet has become more desirable. However, such real-time applications often do not work well across the Internet because of variable queuing delays and congestion losses, and because the Internet, as conceived, offers only a very simple point-to-point, best-effort data delivery. As a result, before real-time applications, such as remote video and multimedia conferencing, can be broadly used, the Internet infrastructure must be modified to support real-time quality of service (QoS), which provides some control over end-to-end packet delays.
Another problem with respect to communication over the Internet involves the communication lines. Long haul communications lines are very expensive to use, and major customers usually contract to pay for the use of these lines according to the amount of “time” they wish to have access to these lines rather than by the amount of traffic they send over them. Consequently, it is very important that these customers make the most efficient use of these lines. To make efficient use of these lines, it is desirable to provide requested/specified asynchronous transfer mode (ATM) QoS for many thousands of virtual channels (VCs) all using the same physical port. In other words, a network should be optimally setup so that traffic meets the specified QoS parameters of any portion of the network.
This setup results in a very large VC cell scheduling problem when some number of VCs have cells available at a network interface for transmission onto the Internet at the same time. These VCs could support constant bit rate (CBR) type traffic, variable bit rate (VBR) traffic, or unspecified bit rate (UBR) traffic. These traffic terms are described in the ATM Forum UNI 4.0 Specification, which also describes other traffic types in addition to CBR, VBR and UBR, such as adjustable bit rate (ABR). When a number of cells arrive at the network interface at the same time, a problem arises with respect to determining the priority in which each of the cells of the various VCs should be scheduled for transmission.
For small numbers of VCs, individual processes implementing the Leaky Bucket algorithm may be implemented for each VC. This algorithm, however, is impractical for large numbers of VCs.
With respect to the Internet protocol (IP) QoS problem, prior art solutions have implemented multiple logical FIFOs to handle variously prioritized packets, typically referred to as “priority queuing.” The queue with the highest priority traffic would always be checked first for an available packet to send and when this queue was emptied, the next priority queue would be checked for available packets to send, and so forth. Such a priority queuing arrangement, however, does not guarantee service to every packet because high priority traffic can “lock out” low priority traffic indefinitely. In contrast, by giving, for example, all users in a packet-scheduling scheme the same priority, but treating the queues in a round robin fashion, packet scheduling guarantees each user a particular committed amount of bandwidth with which other users cannot interfere. Alternatively, each user can have a variable priority based on whether the user has been under or over-utilizing their guaranteed bandwidth. The weighted fair queuing (WFQ) algorithm provides such a scheme.
SUMMARY OF THE INVENTION
A system consistent with the present invention is event driven, the events being packet arrivals and indications of new cell times. Cells are scheduled for transmission one at a time using time-based queues. For VBR traffic, two variables are maintained for each VBR logical channel that represent time values, scheduled departure time (SDT) and theoretical departure time (TDT). These variables are used to calculate queue times for VBR cells that must be rescheduled.
A system consistent with the present invention for scheduling the transmission cells of packet objects, each packet object including at least one cell and associated with a logical channel index (LCI) identifying the logical channel over which a packet object is to be transmitted, said computer system includes at least one memory for storing the packet objects, for storing a queue time (QT) for each packet object, and for storing one of a plurality of traffic types for each packet object, at least one of the traffic types being a predetermined traffic type, a queue manager for enqueuing the packet objects into said memory, and at least one scheduling element for determining the transmission time for each LCI of the predetermined traffic type enqueued in said memory and for rescheduling an LCI of the predetermined traffic type having at least one cell that is not transmitted at its corresponding transmission time.
Both the foregoing general description and the following detailed description provide examples and explanations only. They do not restrict the claimed invention.
REFERENCES:
patent: 5533020 (1996-07-01), Byrn et al.
patent: 5748614 (1998-05-01), Wallmeier
patent: 5793747 (1998-08-01), Kline
patent: 5940397 (1999-08-01), Gritton
patent: 6018527 (2000-01-01), Yin et al.
patent: 6226262 (2001-05-01), Sterne et al.
Carvey Philip P.
Kohalmi Steven
Milliken Walter C.
Partridge Craig
Pettyjohn Ronald L.
Patel Ajit
Phunkulh Bob A.
Suchyta Leonard Charles
Verizon Corporate Services Group Inc.
Weixel James K.
LandOfFree
System and method for scheduling and rescheduling the... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for scheduling and rescheduling the..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for scheduling and rescheduling the... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3178741