loading...
Efficient Reduction of HOL Blocking in Multistage Networks
Denver, Colorado April 04-April 08
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/IPDPS.2005.19319th IEEE International Parallel and ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
T. Nachiondo, Universidad Polit?cnica de Valencia, Spain
J. Flich, Universidad Polit?cnica de Valencia, Spain
J. Duato, Universidad Polit?cnica de Valencia, Spain
Head-of-line blocking is one of the main problems arising in input-buffered switches. The best-known solution to this problem consists of using Virtual Output Queues (VOQs). However this strategy is not scalable. Its implementation cost increases quadratically with the number of ports in the switch. Taking into account current trends, the demand for larger number of ports in high-performance switches is likely to increase very rapidly in the future. Therefore, a scalable and cost-effective solution is required.
In this paper we propose an efficient and cost-effective strategy (belonging to a family of strategies previously proposed, referred to as Destination-Based Buffer Management (DBBM)), to reduce HOL blocking in single-stage and multistage networks. The proposed strategy is based on allowing certain destinations to share the same queue. Its main purpose is to maximize network throughput whereas keeping HOL blocking to negligible values. In this paper, we apply the strategy at every switch included in a bidirectional multistage network (BMIN). We have evaluated DBBM, VOQ, and alternative strategies in different BMIN sizes and with different traffic conditions (synthetic traffic, IP traces, and I/O traces). Results show that DBBM with a reduced number of queues at each switch obtains roughly the same throughput as the VOQ mechanism. Moreover, VOQ at the switch level (as many queues as output ports at every switch) has also been analyzed. Results demonstrate that it does not scale. As the number of stages in the network increases, the VOQ solution at the switch level introduces more HOL blocking that leads to a severe degradation in network throughput. With the DBBM using 16 queues, maximum network throughput is sustained for all the traffic cases analyzed. Moreover, as the network size increases (up to a 2048?2048BMIN), DBBM keeps roughly the same performance with the same number of queues.
Citation:
T. Nachiondo, J. Flich, J. Duato, "Efficient Reduction of HOL Blocking in Multistage Networks," ipdps, vol. 10, pp.211b, 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Workshop 9, 2005
Usage of this product signifies your acceptance of the Terms of Use.