Network routing capacity

被引：49

作者：

Cannons, J ^{[1
]}

Dougherty, R

Freiling, C

Zeger, K

机构：

[1] Univ Calif San Diego, Dept Elect & Comp Engn, La Jolla, CA 92093 USA

[2] Ctr Commun Res, San Diego, CA 92121 USA

[3] Calif State Univ San Bernardino, Dept Math, San Bernardino, CA 92407 USA

来源：

IEEE TRANSACTIONS ON INFORMATION THEORY | 2006年 / 52卷 / 03期

基金：

美国国家科学基金会;

关键词：

network coding; capacity; switching; flow;

D O I：

10.1109/TIT.2005.864474

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We define the routing capacity of a network to be the supremum of all possible fractional message throughputs achievable by routing. We prove that the routing capacity of every network is achievable and rational, we present an algorithm for its computation, and we prove that every rational number in (0, 1] is the routing capacity of some solvable network. We also determine the routing capacity for various example networks. Finally, we discuss the extension of routing capacity to fractional coding solutions and show that the coding capacity of a network is independent of the alphabet used.

引用

页码：777 / 788

页数：12

共 24 条

[1] Network information flow [J].

Ahlswede, R ;

Cai, N ;

Li, SYR ;

Yeung, RW .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2000, 46 (04) :1204-1216

[2]

[Anonymous], 2002, 1 COURSE INFORM THEO

[3]

[Anonymous], 2003, 51 ALL C COMM CONTR

[4]

CHEKURI C, UNPUB IEEE T INF THE

[5] Insufficiency of linear coding in network information flow [J].

Dougherty, R ;

Freiling, C ;

Zeger, K .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2005, 51 (08) :2745-2759

[6] Linearity and solvability in multicast networks [J].

Dougherty, R ;

Freiling, C ;

Zeger, K .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2004, 50 (10) :2243-2256

[7]

DOUGHERTY R, IN PRESS IEEE T INFO

[8]

FEDER M, 2003, EL C COMP COMPL ECCC, P1

[9]

Ho T, 2003, 2003 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY - PROCEEDINGS, P441

[10]

Hwang F., 1992, ANN DISCRETE MATH, P53

← 1 2 3 →