Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Prioritized data routing
Reexamination Certificate
1998-06-09
2001-06-12
Harrell, Robert B. (Department: 2756)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Prioritized data routing
C709S226000, C709S235000, C340S870030, C370S230000
Reexamination Certificate
active
06247061
ABSTRACT:
BACKGROUND OF THE INVENTION
1. The Field of the Invention
The field of the present invention is that of scheduling network communication packets for delivery onto a communications network. More specifically, a stream of packets requiring certain resource requirements, such as sound or video data in a multimedia application, are scheduled such that the service requirements for proper processing of packetized data may be met on the receiving end of the network connection.
2. Present State of the Art
Over time, the usefulness and benefits of stand alone computing devices, such as the ubiquitous personal computer, have been leveraged by allowing many of such computing devices to communicate one with another over a communications network. Network communication between computers allows many different kinds of applications to exist that are otherwise not possible with a stand alone computing device.
For communicating over a network, information that is to be transported from one computer to another is divided into a number of network communication packets. These network packets (also known simply as “packets”) will eventually be transported across physical communications network. In the PC environment, transmission is handled by a network interface card residing in the personal computer. Throughout this application, the PC environment will be assumed though the discussion and application of the concepts applied to many different network computing environments as will be appreciated by those skilled in the art.
Initially, simple file transfers and messaging, such as e-mail, between networked computers constituted one major form of useful applications. Delays due to network traffic had little impact on the quality of service for such applications since a relatively long delay could be sustained without irritation on the part of the end user.
Currently, multimedia applications will have streaming data that is communicated from one computer to another such as successive sound or video frames. Such streaming data must be processed on a rate basis at the destination node and that same rate should be maintained for packet delivery over the network connection. Streaming data typically refers to a continuous set of successive packets that, in order to be processed correctly at the receiving computer, must have certain guaranteed transmission characteristics.
In other words, the packets should be sent at a certain rate with a certain limitation on the amount of variability between when successive packets are sent. Otherwise, packets will not be received and processed appropriately by the receiving computer and perceptible errors occur from the perspective of the end user. For example, a video frame may be lost or temporarily frozen if there is some sort of interruption in the stream of packets being processed.
In order to assure a certain quality of service, reservation of network bandwidth or other relevant resource is required. A number of different protocols have been developed, such as RSVP, ATM, etc., for making bandwidth reservations on all nodes that would be in charge of carrying network communication packets between the source and destination nodes. In this manner, once the bandwidth reservations are made, the packets may be sent as part of a data stream from the source node to the destination node with the assurance that a certain quality of service will result due to the bandwidth reservation.
When a packet data stream is associated with some form of resource guarantee or allocation, such as a bandwidth reservation, it is said to be a packet flow. In order to meet the service requirements for a data stream one or more packet flows can be established between the networked nodes. Packets are scheduled for delivery onto the communications network from the origination node based on the data streams quality of service requirements. Therefore, many different packet scheduling algorithms have been developed depending on different scenarios and requirements. Furthermore, this is an area of ongoing research such that other algorithms that are not yet known may be used in the future for ensuring quality of service requirements.
A live audio-video connection that is sent over the Internet or other packet switching network is an example of a data stream having quality of service requirements. Such an audiovisual data stream may occur as part of a video-telephone and would require that the information be delivered quickly and without too much delay so that quality pictures and sound could be perceived by the end user. When quality of service requirements are not met in such an application, a jerky or frozen image may result or the picture and sound may appear too unnatural for interaction due to delay.
The quality of service for a data stream that is transported over a communications network is transformed into a flow of packets, where the packets are scheduled for delivery onto the network in such a manner that the quality of service characteristics can be met. What is needed is a flexible packet scheduling mechanism that allows different algorithms to be supported for each packet flow. In this manner, the particular requirements or situation for a given packet flow can be adapted to the best suited algorithm. Furthermore, such a packet scheduling mechanism should also be extensible so that it may incorporate new scheduling algorithms as may be developed in the future. In this manner, many possible algorithms may be supported so that many potential algorithms may coexist on the same machine and be used for meeting quality of service requirements for different packet flows.
SUMMARY AND OBJECTS OF THE INVENTION
It is an object of the present invention to provide a flexible packet scheduling mechanism that supports multiple scheduling algorithms.
It is another object of the present invention to deliver packets from a packet flow over communications in such a manner that service quality requirements for a data stream are met.
It is yet another object of the present invention to assign a conformance time to a packet representing a time for an action to take place in order to have that packet conform to a service requirement and that may be used by one or more other components processing the packet at a later point in time.
Additional objects and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by the practice of the invention. The objects and advantages of the invention may be realized and obtained by means of the instruments and combinations particularly pointed out in the appended claims.
To achieve the foregoing objects, and in accordance with the invention as embodied and broadly described herein a method and computer program product for scheduling network communication packets originating from different streams having unique service requirements is provided. The present invention overcomes the limitations in the prior art by dividing the packet scheduling function into distinct components that may be implemented as separate drivers in a layered driver environment as exists, for example, in the Microsoft Windows NT operating system or implemented in other ways as part of the protocol stack.
One component is called a conformer and will generate and assign to each packet in the packet flow at least one conformance time that signifies the earliest time at which a packet may be sent while still conforming to the network resource requirements associated with the flow. Many different conformance algorithms can be supported so that the best algorithm is used for a particular packet flow and the service requirements that it represents. The conformer may also be used to discard packets whose conformance times are greater than the current time such that they are considered dropped.
A general or default conformance algorithm is provided that handles many current constraints in an acceptable manner. The default conformance algorithm implements a token bucket algorithm for setting the conformance time with res
Bar Ofer
Bell Carol Ann
Bernet Yoram
Douceur John R.
Tai Tsung-Yuan Charles
Harrell Robert B.
Microsoft Corporation
Willett Stephan
Workman & Nydegger & Seeley
LandOfFree
Method and computer program product for scheduling network... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and computer program product for scheduling network..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and computer program product for scheduling network... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2505015