On robust network coding subgraph construction under uncertainty
Abstract
We consider the problem of network coding subgraph construction in networks where there is uncertainty about link loss rates. For a given set of scenarios specified by an uncertainty set of link loss rates, we provide a robust optimization-based formulation to construct a single subgraph that would work relatively well across all scenarios. We show that this problem is coNP-hard in general for both objectives: minimizing cost of subgraph construction and maximizing throughput given a cost constraint. To solve the problem tractably, we approximate the problem by introducing path constraints, which results in polynomial time-solvable solution in terms of the problem size. The simulation results show that the robust optimization solution is better and more stable than the deterministic solution in terms of worst-case performance. From these results, we compare the tractability of robust network design problems with different uncertain network components and different problem formulations.
Additional Information
© 2008 IEEE. This work has been supported in part by subcontract #069144 issued by BAE Systems National Security Solutions, Inc. and supported by the Defense Advanced Research Projects Agency (DARPA) and the Space and Naval Warfare System Center (SPAWARSYSCEN), San Diego under Contracts No. N66001-08-C-2013 and W911NF-07-1-0029, and by Caltech's Lee Center for Advanced Networking.Attached Files
Published - Chang2008p83592008_42Nd_Asilomar_Conference_On_Signals_Systems_And_Computers_Vols_1-4.pdf
Files
Name | Size | Download all |
---|---|---|
md5:07648a72107fbd50a44fec43f731abbc
|
352.5 kB | Preview Download |
Additional details
- Eprint ID
- 19166
- Resolver ID
- CaltechAUTHORS:20100722-131717463
- 069144
- BAE Systems National Security Solutions, Inc.
- Defense Advanced Research Projects Agency (DARPA)
- N66001-08-C-2013
- Space and Naval Warfare System Center (SPAWARSYSCEN), San Diego
- W911NF-07-1-0029
- Space and Naval Warfare System Center (SPAWARSYSCEN), San Diego
- Caltech Lee Center for Advanced Networking
- Created
-
2010-07-30Created from EPrint's datestamp field
- Updated
-
2021-11-08Created from EPrint's last_modified field
- Series Name
- Conference Record of the Asilomar Conference on Signals, Systems and Computers
- Other Numbering System Name
- INSPEC Accession Number
- Other Numbering System Identifier
- 10718992