Document Type

Technical Report

Publication Date

2003-06-30

Filename

wucse-2003-48.pdf

Technical Report Number

WUCSE-2003-48

Abstract

Multistage interconnection networks with internal cell buffering and dynamic routing are among the most cost-effective architectures for multi-terabit internet routers. One of the key design issues for such systems is maintaining cell ordering, since cells are subject to varying delays as they pass through the interconnection network. The most flexible and scalable approach to cell resequencing uses timestamps and a time-ordered resequencing buffer at each router output port. Conventional, fixed-threshold resequencers can perform poorly in the presence of extreme traffic conditions. This paper explores alternative resequencer designs that are more tolerant of such traffic. These alternatives include a novel adaptive resequencer that adjusts the time cells spend waiting in the resequencing buffer, based on the recent history of the interconnection network delay. The design is straightforward to implement and requires only constant time per cell, making it suitable for systems with link speeds of up to 40 Gb/s. We show that the combination of adaptive resequencing and appropriately designed inter-connection networks can limit resequencing errors to negligible levels without requiring large resequencing latencies.

Comments

Permanent URL: http://dx.doi.org/10.7936/K77M068P

Download

Share

COinS