PHENOMENON OF HIGHER-ORDER HEAD-OF-LINE BLOCKING IN MULTISTAGE INTERCONNECTION NETWORKS UNDER NONUNIFORM TRAFFIC PATTERNS

Nonuniform traffic can degrade the overall performance of multistage i nterconnection networks substantially. In this paper, this performance degradation is traced back to blocking effects that are not present u nder uniform traffic pat terns within a network. This blocking phenome non is not mentioned in the literature and is termed higher order Head -of-Line-blocking (HOL(k)-blocking) in this paper. Methods to determin e the HOL-blocking order of multistage networks in order to classify t he networks are presented. The performance of networks under hot-spot traffic as a function of their HOL-blocking characteristics is studied by simulation. It is shown that network bandwidth and packet delay im prove under nonuniform traffics with increasing HOL-blocking order of a network.