Scheduling network applications based on divisible load theory (DLT)

The next generation Internet is being designed to serve diverse content-aware applications instead of passively carrying packets from one node to another. These services demand service-differentiated and application-oriented processing at network nodes with quality of service (QoS) provision. Given the processing power limitation of single computing device and the inherent parallelism associated with network traffic, distributed processing is becoming increasingly attractive. In this dissertation, we present our research work on application level load balancing and message scheduling inside a network with the objective of satisfying the QoS requirement of differentiated services while maximizing the resource utilizations.;Cisco Systems' Application Oriented Networking (AON) is an important network equipment towards building next generation service oriented intelligent information network. AON recognizes and processes application-level content and allows more advanced message-level load balancing mechanisms to be deployed in front of a heterogeneous server cluster. We propose and implement an intelligent message-type based adaptive scheduling algorithm into AON. The experimental study shows its superiority over existing schemes due to the service type awareness.;AON devices offer increasing level of application awareness in network infrastructure. Application oriented services often carry stringent performance requirements, which are increasingly handled by multi-core processors. The content processing of AON demands critical computation power. Multi-processor architecture helps to boost overall processing capacity. The workload scheduling among these processors may employ traditional round-robin scheme and its variants that are simple to implement and guarantee fairness. However, they also introduce a high packet out-of-order rate which should be avoided for multimedia and other order-sensitive applications. We propose a novel scheduling algorithm, Ordered Round Robin (ORR), based on the divisible load theory (DLT). Its ideal model entirely eliminates the out of sequence problem while maintaining an optimal overall throughput.;When a single network element, e.g., AON, cannot cope with the demanded workload, "borrowing" processing power from other nodes within the network becomes a natural solution. Inside a network where multiple heterogeneous network nodes are connected via heterogeneous links, we propose a strategy on cycle donation and consumption of computing power at each processing node. Our scheduler, based on Divisible Load Theory (DLT), builds a dynamic multi-level resource tree that provides minimal yet sufficient power for the target job, which makes it particularly desirable for real-time or deadline-driven tasks.