Data Scheduling

  When using dial-up serial links for data transmission, bandwidth may be considered a scarce resource. Not only is the bandwidth provided by serial interfaces an order of magnitude less than that of LAN interfaces, the cost of communication and the availability of physical connections also limit the time, that a serial interface may be kept up.

The objective of data scheduling is partly to ensure that most important data are sent first, partly to ensure that any transmission is cost efficient. The data scheduling applies to data sent between the mobile host and the MSG. The approach presented here relies on the TACO layer to schedule data for transmission. It is based on the applications providing with each Transmission EndPoint (TEP) a set of requirements, which describes the desired link to use for transmitting data associated with this TEP. The set consists of:

1. Minimum Required Bandwidth (MRB)  
2. Maximal Latency (ML)  
3. Maximal Cost per Minute (MCM)  
4. Minimal Idle Time before disconnect (MIT)  
5. Preferable maximum Time before Connect (PTC)  

Interface profiles with respect to items 1 through 3 are specified for different communication interfaces (GSM modem, ordinary modem, Ethernet) based on technical specifications of the interfaces.

The scheduling approach is based on three data structures, a wait queue, an active set, and a pending set. Each active TEP is represented by a data queue in one of these structures. Any data sent will be appended to the corresponding TEP queue. If no queue is associated with the TEP in any of the data structures, a new queue will be created and placed in either the wait queue, the active set, or the pending set depending on the requirements set associated with the TEP.

Wait Queue Any new TEP queue will be placed here, whenever PTC > 0. It will remain here until the timer value reaches 0. When a timeout occurs, the corresponding TEP queue is moved to either the active set or the pending set, depending on whether or not items 1 through 3 of the requirements set match the current interface profile. In case of a match, the queue is moved to the active set structure, otherwise it is moved to the pending set.

Active Set Any TEP queue, where PTC = 0, will appear in the active set as long as the queue is non-empty and MIT > 0. When a MIT timeout occurs, the corresponding empty TEP queue is deleted from the active set. In case a change in interface profile occurs, any queues, where items 1 through 3 of the related requirements set do not match the new interface profile, will be moved to the pending set. The idle timer of a physical link is set to the maximum MIT among TEPs in the active set, and will be adjusted as the active set changes.

Pending Set Any TEP queue where PTC = 0 and the items 1 through 3 of the related requirements set do not match the interface profile, will appear in the pending set. In case a change in interface profile occurs, any queues, where items 1 through 3 of the related requirements set do match the new interface profile, will be moved to the active set.

Since link requirements are associated with TEPs rather than packets, all packets sent on a given TEP will have identical link requirements. This means that within TEPs, packets can be scheduled on a simple FIFO basis. The scheduling among TEPs in the active set, is done round robin, allowing a TEP granted access to the communication interface, to send one packet only from it's associated data queue. This ensures that no TEP falls subject to starvation, but bandwidth is not necessarily divided equally among TEPs, as packets from the various TEP queues may differ in size.

A physical link is established whenever the active set becomes non-empty, and taken down when the idle timer of the physical link generates a timeout. Involuntary disconnects cause attempts to reconnect whenever at least one of the TEPs in either the active set or the pending set has it's requirements matched by the interface profile (the reason for searching the pending set is, that disconnects might occur due to a change of interface).

Unused bandwidth will be utilized transmitting data from any TEP from either the wait queue or the pending set. Since all TEPs within the pending set have link requirements not matched by the interface profile, data related with these connections are only sent if no TEPs from the wait queue matches the interface profile. Any transmission initiated to utilize spare bandwidth leaves the idle timer, associated with the physical link, unaffected.

During periods of disconnectivity, application level protocols may retransmit packets, causing a large number of duplicate packets to be buffered in the TEP queues. To remedy this, we allow the user to specify, that IP packets for certain TEPs should be discarded during disconnected operation.

The advantages of the scheduling approach are:

• Specification of link requirements is a very natural way to state the communication needs of an application, with respect to, e.g., cost efficiency and responsiveness.
• Selection of the next packet to send is made very simple, since it requires only the next TEP eligible for transmission be selected. Once a TEP is found the packet to send from the TEP queue is given.
• Reordering of TEPs among scheduling structures due to a change in communication interface or PTC timeouts induces very little overhead. The number of TEPs is typically an order of magnitude less than the number of packets, so operating on entire groups of data packets has a significant impact on the efficiency of the scheduling approach.
• Starvation is non-existent.

The disadvantages of the approach are:

• Bandwidth is not divided equally among TEPs in the active set, since the scheduling mechanism does not take into account the size of data packets in the various TEP queues. This might cause interactive applications (e.g., telnet) to suffer a loss in responsiveness, if the active set contains TEPs from applications sending data in large chunks (e.g., ftp).
• The time parameter given by item 5 in the requirements set might be difficult to specify. The PTC parameter states the time an application is willing to postpone the initiation of a data transmission, but there is no guarantee that a transmission can be started within the time frame set by the PTC. A small PTC will ensure the application, that as soon as an appropriate communication interface is available, data transmission will be started. The size of the PTC parameters, however, influence the effectiveness of the scheduling mechanism. The tradeoff made between the effectiveness of the scheduling mechanism and the likelihood that the data transmission is commenced within the time frame required, is not at all obvious when setting the PTC.