NDLI: Network Coding in a Multicast Switch

Content Provider	IEEE Xplore Digital Library
Author	Minji Kim Sundararajan, J.K. Médard, M. Eryilmaz, A. Kötter, R.
Copyright Year	1963
Abstract	The problem of serving multicast flows in a crossbar switch is considered. Intraflow linear network coding is shown to achieve a larger rate region than the case without coding. A traffic pattern is presented which is achievable with coding but requires a switch speedup when coding is not allowed. The rate region with coding can be characterized in a simple graph-theoretic manner, in terms of the stable set polytope of the "enhanced conflict graph". No such graph-theoretic characterization is known for the case of fanout-splitting without coding. The minimum speedup needed to achieve 100% throughput with coding is shown to be upper bounded by the imperfection ratio of the enhanced conflict graph, where the imperfection ratio measures a certain graph theoretic property of the given graph. When applied to K × N switches with unicasts and broadcasts only, this gives a bound of min(2K-1/K, 2N/N+1) on the speedup. This shows that speedup, which is usually implemented in hardware, can often be substituted by network coding, which can be done in software. Computing an offline schedule (using prior knowledge of the flow rates) is reduced to fractional weighted graph coloring. A graph-theoretic online scheduling algorithm (using only queue occupancy information) is also proposed, that stabilizes the queues for all rates within the rate region.
Sponsorship	IEEE Information Theory Society
Starting Page	436
Ending Page	460
Page Count	25
File Size	681655
File Format	PDF
ISSN	00189448
Volume Number	57
Issue Number	1
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2011-01-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Switches Network coding Encoding Unicast Throughput Schedules Fabrics speedup Imperfection ratio multicast switch network coding rate region scheduling
Content Type	Text
Resource Type	Article
Subject	Library and Information Sciences Information Systems Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Rate Quantization and the Speedup Required to Achieve 100% Throughput for Multicast Over Crossbar Switches

Asymptotic Performance Limits of Switches With Buffered Crossbars Supporting Multicast Traffic

An Analysis of Blocking Switches Using Error Control Codes

A Geometric Perspective to Multiple-Unicast Network Coding

The Complexity of Network Coding With Two Unit-Rate Multicast Sessions

A Constant Bound on Throughput Improvement of Multicast Network Coding in Undirected Networks

Bounding the Coding Advantage of Combination Network Coding in Undirected Networks

Multicasting in Linear Deterministic Relay Network by Matrix Completion

The encoding complexity of network coding

Network Coding in a Multicast Switch

Similar Documents

Rate Quantization and the Speedup Required to Achieve 100% Throughput for Multicast Over Crossbar Switches

Asymptotic Performance Limits of Switches With Buffered Crossbars Supporting Multicast Traffic

An Analysis of Blocking Switches Using Error Control Codes

A Geometric Perspective to Multiple-Unicast Network Coding

The Complexity of Network Coding With Two Unit-Rate Multicast Sessions

A Constant Bound on Throughput Improvement of Multicast Network Coding in Undirected Networks

Bounding the Coding Advantage of Combination Network Coding in Undirected Networks

Multicasting in Linear Deterministic Relay Network by Matrix Completion

The encoding complexity of network coding

Network Coding in a Multicast Switch