Abstract: With the increase
of internet protocol (IP) packets the performance of routers became an
important issue in internetworking. In this paper we examine the matching
algorithm in gigabit router which has input queue with virtual output queueing.
Dynamic queue scheduling is also proposed to reduce the packet delay and
packet loss probability.
Port partitioning is employed to
reduce the computational burden of the scheduler in a switch which matches
the input and output ports for fast packet switching. Each port is
divided into two groups such that the matching algorithm is implemented
within each pair of groups in parallel. The matching is performed by exchanging
the pair of groups at every time slot. Two algorithms, maximal weight matching
by port partitioning (MPP) and modified maximal weight matching by port
partitioning (MMPP) are presented. In dynamic queue scheduling, a pop-up
decision rule for each delay critical packet is made to reduce both the
delay of the delay critical packet and the loss probability of loss critical
packet.
Computational results show that
MMPP has the lowest delay and requires the least buffer size. The throughput
is illustrated to be linear to the packet arrival rate, which can be achieved
under highly efficient matching algorithm. The dynamic queue scheduling
is illustrated to be highly effective when the occupancy of the input buffer
is relatively high.