An O(N log N) Fair Multicast Packet Switch with Low Memory Requirements

Rajgopal KANNAN  Sibabrata RAY  

Publication
IEICE TRANSACTIONS on Communications   Vol.E84-B    No.12    pp.3252-3264
Publication Date: 2001/12/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Network
Keyword: 
ATM switch,  multicasting,  output queueing,  deflection routing,  

Full Text: PDF(1.9MB)>>
Buy this Article


Summary: 
We propose an efficient, low cost, multicast ATM switch which is fair to all inputs. The switch consists of a novel copy network which creates unicast packets in a fair manner, followed by a network that routes packets to their correct Address Translation Tables (ATT's) and ultimately a unicast routing network which ensures sequencing. The copy and routing networks are based on deflection routing. We show that our switch requires O(log N) stages and can be designed for any arbitrarily low level of packet loss. The theoretical results are backed up by simulations. Switching elements in both the copying and routing networks have O(1) bit complexity, making the overall bit level hardware complexity of the network O(N log N). The latency of the switch is proportional to the number of stages O(log N). Unlike other existing copy networks, our copy network drops packets in a fair manner and hence can provide quality of service (QoS) support. The switch is output queued and allows the delivery of multiple packets to the same destination during a time slot.