The aim of this topic is to develop a common framework for analyzing capacities of wireline and wireless networks. Our focus will, in fact, be on physical- and link-layer issues for wireless problems. However, there are close relations between wireline and wireless networks that we wish to highlight, and that we hope will lead to a better understanding of both types of networks.
As is customary, we will represent a network by a graph, i.e., a set N of nodes and a set E of edges that are pairs of nodes (see Figure 1.1). If an edge (u,v) is directed, then the ordering tells us that the edge goes from node u to node v. For example, the directed network in Figure 3.1 below has N = {1,2,3} and E = {(1,2), (2,3)}.
The channels (or edges) of a wireline network are usually modeled as being independent in the sense that the signals carried by different channels do not interfere with each other (see Table 1.1). Moreover, one often assumes that any noise has been removed by ARQ and FEC at the PHY layer. The resulting network is hence noise free, but the edges have capacity constraints due to bandwidth limitations.
Fig. 3.1 A wireline network.
The bandwidths of different channels in a wireline network can differ greatly, e.g., if the channels represent copper wires or fiber-optic cables. The channels usually change slowly so that nodes can learn their channels during an initialization phase. However, the nodes may be aware of only the local topology of the network. A common approach is to organize data into packets that are sometimes lost, e.g., due to congestion, in which case one encounters packet erasures.
A simple such network with three nodes and two edges is shown in Figure 3.1 where the signal carried on the edge between nodes 1 and 2 is labeled X12, and similarly for X23. Suppose the capacities of the first and second edges are C12 and C23 bits per channel use, respectively. As an abstraction, we choose the alphabets of X12 and X23 to have sizes 2Cl2 and 2C23 (assumed to be integers), respectively. One can, therefore, transmit at most Ce bits through edge e every time one uses this edge.
A wireline network often has delay, processing, and input/output constraints on the nodes. For instance, suppose node 2 in Figure 3.1 has limited processing power. We could model this as shown in Figure 3.2 where, as compared to Figure 3.1, node 2 is split into two nodes and an edge carrying X2 that has an alphabet of size 2C2.
Fig. 3.2 A wireline network with a node constraint.
Fig. 3.3 A wireline network with another type of node constraint.
Consider next a second type of node constraint where node 2 in Figure 3.1 has only one input/output port on which it can either transmit or receive. We model this as shown in Figure 3.3: we introduce input and output variables Xu and YU, respectively, for every node u and write
while for node 3 we have Y3 = X2. The symbol 0 in (3.1) might represent a "silence" symbol. The abstraction in (3.1) will later help to define information-theoretic models for wireless networks as well.
As a somewhat more complex example, consider the network shown in Figure 3.4 where both nodes 1 and 2 have port constraints as in (3.1). We write the resulting network equations as Y13 = X13, Y23 = X23, and
Note that the network in Figure 3.4 has two paths to node 3 from nodes 1 and 2, rather than just one as in Figure 3.1. We can thus use more sophisticated communication strategies for the network of Figure 3.4 than for the network in Figure 3.1. Note further that, for wireline networks, it is often useful to give the edge variables two indices, one index for the "start" node and one for the "end" node.
Fig. 3.4 Another wireline network.
