The Experts below are selected from a list of 27309 Experts worldwide ranked by ideXlab platform
K Zeger - One of the best experts on this subject based on the ideXlab platform.
-
Unachievability of network coding Capacity
IEEE Transactions on Information Theory, 2006Co-Authors: Randall Dougherty, Chris Freiling, K ZegerAbstract:The coding Capacity of a network is the supremum of ratios k/n for which there exists a fractional (k, n) coding solution, where k is the source message dimension and n is the maximum edge dimension. The coding Capacity is referred to as Routing Capacity in the case when only Routing is allowed. A network is said to achieve its Capacity if there is some fractional (k, n) solution for which k/n equals the Capacity. The Routing Capacity is known to be achievable for arbitrary networks.We give an example of a network whose coding Capacity (which is 1) cannot be achieved by a network code. We do this by constructing two networks, one of which is solvable if and only if the alphabet size is odd, and the other of which is solvable if and only if the alphabet size is a power of 2. No linearity assumptions are made.
-
Network Routing Capacity
IEEE Transactions on Information Theory, 2006Co-Authors: J Cannons, Randall Dougherty, Chris Freiling, K ZegerAbstract: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
-
network Routing Capacity
International Symposium on Information Theory, 2005Co-Authors: J Cannons, Randall Dougherty, Chris Freiling, K ZegerAbstract: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 non-negative rational number is the Routing Capacity of some 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
-
ISIT - Network Routing Capacity
Proceedings. International Symposium on Information Theory 2005. ISIT 2005., 2005Co-Authors: J Cannons, Randall Dougherty, Chris Freiling, K ZegerAbstract: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 non-negative rational number is the Routing Capacity of some 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
Randall Dougherty - One of the best experts on this subject based on the ideXlab platform.
-
Unachievability of network coding Capacity
IEEE Transactions on Information Theory, 2006Co-Authors: Randall Dougherty, Chris Freiling, K ZegerAbstract:The coding Capacity of a network is the supremum of ratios k/n for which there exists a fractional (k, n) coding solution, where k is the source message dimension and n is the maximum edge dimension. The coding Capacity is referred to as Routing Capacity in the case when only Routing is allowed. A network is said to achieve its Capacity if there is some fractional (k, n) solution for which k/n equals the Capacity. The Routing Capacity is known to be achievable for arbitrary networks.We give an example of a network whose coding Capacity (which is 1) cannot be achieved by a network code. We do this by constructing two networks, one of which is solvable if and only if the alphabet size is odd, and the other of which is solvable if and only if the alphabet size is a power of 2. No linearity assumptions are made.
-
Network Routing Capacity
IEEE Transactions on Information Theory, 2006Co-Authors: J Cannons, Randall Dougherty, Chris Freiling, K ZegerAbstract: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
-
network Routing Capacity
International Symposium on Information Theory, 2005Co-Authors: J Cannons, Randall Dougherty, Chris Freiling, K ZegerAbstract: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 non-negative rational number is the Routing Capacity of some 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
-
ISIT - Network Routing Capacity
Proceedings. International Symposium on Information Theory 2005. ISIT 2005., 2005Co-Authors: J Cannons, Randall Dougherty, Chris Freiling, K ZegerAbstract: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 non-negative rational number is the Routing Capacity of some 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
J Cannons - One of the best experts on this subject based on the ideXlab platform.
-
Topics in network communications
2008Co-Authors: J CannonsAbstract:This thesis considers three problems arising in the study of network communications. The first two relate to the use of network coding, while the third deals with wireless sensor networks. In a traditional communications network, messages are treated as physical commodities and are routed from sources to destinations. Network coding is a technique that views data as information, and thereby permits coding between messages. Network coding has been shown to improve performance in some networks. The first topic considered in this thesis is the Routing Capacity of a network. We formally define the Routing and coding capacities of a network, and determine the Routing Capacity for various examples. Then, 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 show that the coding Capacity of a network is independent of the alphabet used. The second topic considered is the network coding Capacity under a constraint on the total number of nodes that can perform coding. We prove that every non-negative, monotonically non-decreasing, eventually constant, rational-valued function on the non- negative integers is equal to the Capacity as a function of the number of allowable coding nodes of some directed acyclic network. The final topic considered is the placement of relays in wireless sensor networks. Wireless sensor networks typically consist of a large number of small, power-limited sensors which collect and transmit information to a receiver. A small number of relays with additional processing and communications capabilities can be strategically placed to improve system performance. We present an algorithm for placing relays which attempts to minimize the probability of error at the receiver. We model communication channels with Rayleigh fading, path loss, and additive white Gaussian noise, and include diversity combining at the receiver. For certain cases, we give geometric descriptions of regions of sensors which are optimally assigned to the same, fixed relays. Finally, we give numerical results showing the output and performance of the algorithm
-
Network Routing Capacity
IEEE Transactions on Information Theory, 2006Co-Authors: J Cannons, Randall Dougherty, Chris Freiling, K ZegerAbstract: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
-
network Routing Capacity
International Symposium on Information Theory, 2005Co-Authors: J Cannons, Randall Dougherty, Chris Freiling, K ZegerAbstract: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 non-negative rational number is the Routing Capacity of some 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
-
ISIT - Network Routing Capacity
Proceedings. International Symposium on Information Theory 2005. ISIT 2005., 2005Co-Authors: J Cannons, Randall Dougherty, Chris Freiling, K ZegerAbstract: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 non-negative rational number is the Routing Capacity of some 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
Chris Freiling - One of the best experts on this subject based on the ideXlab platform.
-
Unachievability of network coding Capacity
IEEE Transactions on Information Theory, 2006Co-Authors: Randall Dougherty, Chris Freiling, K ZegerAbstract:The coding Capacity of a network is the supremum of ratios k/n for which there exists a fractional (k, n) coding solution, where k is the source message dimension and n is the maximum edge dimension. The coding Capacity is referred to as Routing Capacity in the case when only Routing is allowed. A network is said to achieve its Capacity if there is some fractional (k, n) solution for which k/n equals the Capacity. The Routing Capacity is known to be achievable for arbitrary networks.We give an example of a network whose coding Capacity (which is 1) cannot be achieved by a network code. We do this by constructing two networks, one of which is solvable if and only if the alphabet size is odd, and the other of which is solvable if and only if the alphabet size is a power of 2. No linearity assumptions are made.
-
Network Routing Capacity
IEEE Transactions on Information Theory, 2006Co-Authors: J Cannons, Randall Dougherty, Chris Freiling, K ZegerAbstract: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
-
network Routing Capacity
International Symposium on Information Theory, 2005Co-Authors: J Cannons, Randall Dougherty, Chris Freiling, K ZegerAbstract: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 non-negative rational number is the Routing Capacity of some 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
-
ISIT - Network Routing Capacity
Proceedings. International Symposium on Information Theory 2005. ISIT 2005., 2005Co-Authors: J Cannons, Randall Dougherty, Chris Freiling, K ZegerAbstract: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 non-negative rational number is the Routing Capacity of some 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
Vaughn Betz - One of the best experts on this subject based on the ideXlab platform.
-
Multiple Dice Working as One: CAD Flows and Routing Architectures for Silicon Interposer FPGAs
IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2016Co-Authors: Ehsan Nasiri, Javeed Shaikh, Andre Hahn Pereira, Vaughn BetzAbstract:Large field-programmable gate array (FPGA) systems with multiple dice connected by a silicon interposer are now commercially available. However, many questions remain concerning their key architecture parameters and efficiency, as the signal count between dice is reduced and the delay between the dice is increased compared with a monolithic FPGA. We modify the versatile place and route (VPR) to target interposer-based FPGAs and investigate placement and Routing changes and incorporating partitioning into the flow to improve results. Our best computer-aided design (CAD) flow reduces the Routing demand for interposer FPGAs with realistic connectivity between dice by 47% and improves the circuit speed by 13% on average. Architecture modifications to add Routing flexibility when crossing the interposer are very beneficial and improve routability by a further 11%. With these CAD and architecture enhancements, we find that if an interposer supplies (between dice) 20% of the Routing Capacity that the normal (within-die) FPGA Routing channels supply, there is only a modest impact on circuit routability. Smaller interposer-Routing capacities do impact routability; however, minimum channel width increases by 70% when an interposer supplies only 10% of the within-die Routing. The interposer also impacts delay, increasing circuit delay by 11% on average for a 1-ns interposer signal delay and a two-die system.
-
FPGA - Cad and Routing architecture for interposer-based multi-FPGA systems
Proceedings of the 2014 ACM SIGDA international symposium on Field-programmable gate arrays - FPGA '14, 2014Co-Authors: Andre Hahn Pereira, Vaughn BetzAbstract:Interposer-based multi-FPGA systems are composed of multiple FPGA dice connected through a silicon interposer. Such devices allow larger FPGA systems to be built than one monolithic die can accomodate and are now commercially available. An open question, however, is how efficient such systems are compared to a monolithic FPGA, as the number of signals passing between dice is reduced and the signal delay between dice is increased in an interposer system vs. a monolithic FPGA. We create a new version of VPR to investigate the architecture of such systems, and show that by modifying the placement cost function to minimize the number of signals that must cross between dice we can reduce Routing demand by 18% and delay by 2%. We also show that the signal count between dice and the signal delay between dice are key architecture parameters for interposer-based FPGA systems. We find that if an interposer supplies (between dice) 60% of the Routing Capacity that the normal (within-die) FPGA Routing channels supply, there is little impact on the routability of circuits. Smaller Routing capacities in the interposer do impact routability however: minimum channel width increases by 20% and 50% when an interposer supplies only 40% and 30% of the within-die Routing, respectively. The interposer also impacts delay, increasing circuit delay by 34% on average for a 1 ns interposer signal delay and a four-die system. Reducing the interposer delay has a greater benefit in improving circuit speed than does reducing the number of dice in the system.
