Comparing Network Coding with Multicommodity Flow for the k-pairs Communication Problem
Given a graph G = (V,E) and k source-sink pairs of vertices, this papers investigates the maximum rate r at which all pairs can simultaneously communicate. We view this problem from two perspectives and compare their advantages. In the multicommodity flow formulation, a solution provides dedicated b...
| Main Authors: | , , |
|---|---|
| Language: | en_US |
| Published: |
2005
|
| Online Access: | http://hdl.handle.net/1721.1/30508 |
| _version_ | 1826193925612765184 |
|---|---|
| author | Harvey, Nicholas J. Kleinberg, Robert D. Lehman, April Rasala |
| author_facet | Harvey, Nicholas J. Kleinberg, Robert D. Lehman, April Rasala |
| author_sort | Harvey, Nicholas J. |
| collection | MIT |
| description | Given a graph G = (V,E) and k source-sink pairs of vertices, this papers investigates the maximum rate r at which all pairs can simultaneously communicate. We view this problem from two perspectives and compare their advantages. In the multicommodity flow formulation, a solution provides dedicated bandwidth r between each source-sink pair. In the information flow formulation, a vertex can transmit a function of the information it received thereby allowing multiple source-sink pairs to share bandwidth. For directed acyclic graphs with n vertices, we show that the rate achievable in the information flow formulation can be a multiplicative factor n larger than the rate achievable in the multicommodity flow formulation. It is well known [5] that for undirected graphs with n vertices, in the multicommodity flow formulation, the maximum rate achievable can be an O(1/log|V|) multiplicative factor smaller than the value of the sparsest cut. We extend this result to show that the maximum rate achievable in the information flow setting can be an O(1/log|V|) multiplicative factor smaller than the sparsest cut value.For directed acyclic graphs G, we define a parameter called the value of the most meager cut which is an upper bound for the maximum rate achievable in the information flow setting.We also present an example illustrating that this upper bound is not always tight. |
| first_indexed | 2024-09-23T09:47:28Z |
| id | mit-1721.1/30508 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T09:47:28Z |
| publishDate | 2005 |
| record_format | dspace |
| spelling | mit-1721.1/305082019-04-10T17:42:02Z Comparing Network Coding with Multicommodity Flow for the k-pairs Communication Problem Harvey, Nicholas J. Kleinberg, Robert D. Lehman, April Rasala Given a graph G = (V,E) and k source-sink pairs of vertices, this papers investigates the maximum rate r at which all pairs can simultaneously communicate. We view this problem from two perspectives and compare their advantages. In the multicommodity flow formulation, a solution provides dedicated bandwidth r between each source-sink pair. In the information flow formulation, a vertex can transmit a function of the information it received thereby allowing multiple source-sink pairs to share bandwidth. For directed acyclic graphs with n vertices, we show that the rate achievable in the information flow formulation can be a multiplicative factor n larger than the rate achievable in the multicommodity flow formulation. It is well known [5] that for undirected graphs with n vertices, in the multicommodity flow formulation, the maximum rate achievable can be an O(1/log|V|) multiplicative factor smaller than the value of the sparsest cut. We extend this result to show that the maximum rate achievable in the information flow setting can be an O(1/log|V|) multiplicative factor smaller than the sparsest cut value.For directed acyclic graphs G, we define a parameter called the value of the most meager cut which is an upper bound for the maximum rate achievable in the information flow setting.We also present an example illustrating that this upper bound is not always tight. 2005-12-22T02:16:27Z 2005-12-22T02:16:27Z 2004-11-24 MIT-CSAIL-TR-2004-078 MIT-LCS-TR-964 http://hdl.handle.net/1721.1/30508 en_US Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory 13 p. 14089646 bytes 597139 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | Harvey, Nicholas J. Kleinberg, Robert D. Lehman, April Rasala Comparing Network Coding with Multicommodity Flow for the k-pairs Communication Problem |
| title | Comparing Network Coding with Multicommodity Flow for the k-pairs Communication Problem |
| title_full | Comparing Network Coding with Multicommodity Flow for the k-pairs Communication Problem |
| title_fullStr | Comparing Network Coding with Multicommodity Flow for the k-pairs Communication Problem |
| title_full_unstemmed | Comparing Network Coding with Multicommodity Flow for the k-pairs Communication Problem |
| title_short | Comparing Network Coding with Multicommodity Flow for the k-pairs Communication Problem |
| title_sort | comparing network coding with multicommodity flow for the k pairs communication problem |
| url | http://hdl.handle.net/1721.1/30508 |
| work_keys_str_mv | AT harveynicholasj comparingnetworkcodingwithmulticommodityflowforthekpairscommunicationproblem AT kleinbergrobertd comparingnetworkcodingwithmulticommodityflowforthekpairscommunicationproblem AT lehmanaprilrasala comparingnetworkcodingwithmulticommodityflowforthekpairscommunicationproblem |