Most packet scheduling algorithms for input-queued switches operate on fixed-sized packets known as cells. In reality, communication traffic in many systems such as Internet runs on variable-sized packets. Motivated by potential savings of segmentation and reassembly, there has been increasing interest in scheduling variable-sized packets in a nonpreemptive manner known as packet-mode scheduling. This paper studies frame-based packet-mode scheduling for better scalability. It first shows that the admissible condition is no longer sufficient for packet-mode scheduling. Then, a relation between the frame size and packet sizes is derived that classifies under what conditions the packet-mode scheduling problem is polynomial solvable or is NP-hard. This relation reveals an interesting result that under various packet size distributions, it may be polynomial solvable even if many different packet sizes occur in the packet set, whereas it may be NP-hard with just two packet sizes present. Finally, as a practical solution, this paper studies how a speedup can help packet-mode scheduling. It is shown that the admissible condition becomes sufficient also when a speedup of two is used. A simple algorithm with a speedup of two is presented.

MPLS (multi-protocol label switching) networks allow multiple LSPs (label-switched paths) be established from a source to a destination to satisfy throughput required by an application. Given a MPLS network, where each link is associated with a maximum available bandwidth, a fundamental traffic engineering problem is how we can find minimum number of paths to achieve the maximum throughput. Optimally solving this problem can save huge amount of valuable network resources including available label space and reduce management complexity. This paper proves that finding a minimal number of LSPs is an NP-hard problem. To deal with this problem, we have studied four approximation algorithms. We found from simulations that the average number of paths produced by all these algorithms grows quite slowly when the network grows large. Moreover, the two algorithms, topological-sort-based maximum-path algorithm and greedy-based maximum-edge algorithm perform better than other algorithms. Between these two algorithms, the greedy-based maximum-edge algorithm is more time-efficient while keeps comparable performance.