A unified algebraic theory of sorting, routing, multicasting, and concentration networks

Author

Li, Shuo-Yen Robert

Author_Institution

Chinese Univ. of Hong Kong, Hong Kong, China

fYear

2012

fDate

21-23 Sept. 2012

Firstpage

1

Lastpage

3

Abstract

Sorters, concentrators, mergers, inserters, and other sorting-style devices are widely applied to communications and computation. A sorter receives input values belonging to an ordered set and permutes them into the monotonic order. It is a special form of a unicast switch where the selection of the I/O connection pattern is determined by the comparison among signal values. In particular, a sorting cell means a 2×2 sorter with just two available I/O connection patterns, called the bar and cross states.

Keywords

algebra; multicast communication; multistage interconnection networks; set theory; sorting; telecommunication network routing; I/O connection pattern; bar states; communication; concentration network; concentrator; cross states; inserter; merger; monotonic order; multicasting; multistage interconnection network; ordered set; routing; signal value; sorter; sorting cell; sorting-style device; unicast switch; unified algebraic theory; Lattices; Multicast communication; Payloads; Routing; Software algorithms; Sorting; Switches;

fLanguage

English

Publisher

ieee

Conference_Titel

Network Infrastructure and Digital Content (IC-NIDC), 2012 3rd IEEE International Conference on

Conference_Location

Beijing

Print_ISBN

978-1-4673-2201-0

Type

conf

DOI

10.1109/ICNIDC.2012.6418845

Filename

6418845