Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Statutory Invention Registration
1999-09-07
2004-05-04
Pihulic, Daniel T. (Department: 3662)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
Statutory Invention Registration
active
H0002103
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates generally to multi-hop networks and more specifically the invention pertains to a system for packet scheduling based on message length.
Network protocols, such as IP or ATM, transport data in packets. The algorithms used by these protocols, for routing, scheduling, flow and access control, are usually designed to satisfy performance measures at the packet level (e.g., average packet delay). However, user applications, such as file transfer (FTP), exchange data messages which are not limited in size to that of a network protocol packet. This separation between the application data and the way in which networks manage that data often results in sub-optimal performance when measured in terms of application layer messages. This paper describes packet scheduling algorithms that attempt to reduce end-to-end message delays by taking into account message information in the scheduling of packets across the network.
Network layer packets are typically limited in size to hundreds or thousands of bits. As a result, data messages are fragmented into multiple packets. These packets are then sent to the network layer protocol for delivery across the network. As the packets traverse the network they are queued at nodes along their way together with packets belonging to other messages. Typically, the network layer has no knowledge of the original message to which a packet belongs and serves them on a First-Come-First-Serve (FCFS) basis.
Serving packets on a FCFS basis may be a reasonable strategy if one is only concerned with packet delays. It is known that in a single node, average queuing delay is the same, regardless of scheduling policy, as long as scheduling is not done on the basis of the packet length. If packets are scheduled on the basis of their length, then it has been shown that a scheduling policy that serves the shortest packet first results in minimum delays. However, from an end user point of view, message delays rather than packet delays is a more important performance measure. These messages can be as short as a few hundreds of bits for a short e-mail, to Giga-bits for an image file. In this paper we are concerned with the end-to-end delays experienced by these higher layer messages.
SUMMARY OF THE INVENTION
The present invention is a system that uses two algorithms for scheduling packets in a multi-hop network. The objective of the algorithms is to reduce end-to-end message (not packet) transmission delays. Both algorithms schedule packet transmissions based on the length of the original message to which the packet belongs. The first algorithm is based on the shortest-message-first principle and the second is based on the shortest-remaining-transmit-time principle. Simulations show that these algorithms can significantly reduce average end-to-end message delays compared to First-Come-First-Serve scheduling.
REFERENCES:
(Scheduling packet transmissions in a multi-hop packet switched network based on message length) Modiano, E. Computer Communications and Networks, 1997. Proceedings, Sixth International Conference on, 1997 pp.: 350-357.
Auton William G.
Pihulic Daniel T.
The United States of America as represented by the Secretary of
LandOfFree
Packet scheduling based on message length does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Packet scheduling based on message length, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Packet scheduling based on message length will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3223520