Networking Protocols

Introduction

The classic representation of a communication network is a graph, as in Figure 1.1, with a set of nodes and edges. The nodes usually represent devices such as a router, a wireless access point, or a mobile telephone. The edges usually represent communication links or channels, for example a fiber-optic cable or a wireless link. Both the devices and the channels may have constraints on their operation. For example, a router might have limited processing power, or perhaps it can accept data from only a few of its ports simultaneously. A fiber-optic link has a limited bandwidth (which can be quite large!). A wireless phone, on the other hand, has limited battery resources and likely wishes to conserve energy. A wireless link can have rapid time variations arising from mobility and multipath propagation of signals. Some of these properties are collected in Table 1.1 and are described in more detail in this text.

Fig. 1.1 A network graph.

Table 1.1 Device and channel properties.

The purpose of a communication network is to enable the exchange of messages between its nodes. These messages, as generated by an application, are organized into data packets. In the traditional model of a network, the nodes operate as store-and-forward packet routers that transmit packets over point-to-point links. However, this model is unnecessarily restrictive as it ignores two important possibilities:

• Node Coding: Nodes can combine, or encode, any of their received information and symbol streams.

• Broadcasting: Nodes overhear the transmissions of other nodes from which they are not required to receive messages.

Node coding is possible in any network, while the ability to overhear transmissions is a property of the physical communication channel. In particular, wireless devices inherently broadcast information in that a signal to a particular receiving node can be overheard by other nodes. Typically, the wireless nodes treat these overheard signals as interference and the system provides mechanisms to mitigate this interference. For example, many second generation cellular phones employ code division multiple access (CDMA) to permit signal decoding in the presence of interference [185]. As a second example, 802.11 x wireless LANs employ a media access control (MAC) protocol that enables nearby nodes to share the broadcast channel by taking turns transmitting. The goal of these multiple access strategies is to ensure that communication over a link is reliable. A consequence is that the paradigm of a network as a set of point-to-point communication links is reinforced.

On the other hand, it has been understood in the information theory community for over three decades that wireless communication from a source to destination can benefit from the cooperation of nodes that overhear the transmission. As these intermediate nodes may generate transmissions based on processing of the overheard signals, the signaling strategies go well beyond the inherent cooperation offered by nodes that act as store-and-forward packet routers.

The relay channel [181] models this communication situation. Fundamental coding strategies for the relay channel were developed in [33]. The key idea was that the relay can use the overheard transmission from the source to form its own transmission that aids in decoding at the receiver. These pioneering efforts focused on the simplest case of one source, one destination, and one relay.

More recently, the seminal work of [4] has spurred progress in network coding. The connection between relaying and network coding is that both approaches represent cooperative techniques. A node processes either received signals (in the case of relaying) or messages and encoded packets (in the case of network coding) based on the transmissions of multiple nodes. Although final capacity results remain elusive, it has become apparent that cooperative techniques using node coding and broadcasting offer significant improvements over traditional store-and-forward wireless networks with point-to-point links.

Networking Protocols

Advances in cooperative communication have focused on two goals:

• increasing the communication rates across the network, and

• increasing the communication reliability in networks with time varying channels.

The advances are often demonstrated by mathematical (information theory) analyses of signaling strategies over models of communication channels. The signaling strategies typically involve coordinated transmissions by multiple network nodes; but despite recent progress, there remain significant barriers to applying these results to the development of practical network protocols.

For example, many information-theory results are based on asymptotically large block lengths and usually ignore the overhead needed to set up and maintain coordinated transmissions. In practice, however, and in particular for mobile wireless networks, the time variations in the communication channels necessitate variations in the signaling strategies. The setup and maintenance signaling therefore becomes a recurring cost. We use the term network protocol for a set of distributed algorithms executed by the network nodes that configure, execute, and reconfigure signaling strategies in response to temporal variations. A cooperative network protocol must incorporate methods so that recurring setup costs do not dominate the efficiency gains of a cooperative signaling strategy.

Much of the value of networking is derived from the interconnection of heterogeneous devices and systems. It is worthwhile to keep in mind that the Internet is not so much a network as a network of networks. These interconnections of networks are made possible by designing protocols based on abstract models, as in the layers of the OSI or TCP/IP network protocol stacks [18]. In particular, a network protocol is more valuable by providing a certain capability over a more generic network abstraction, even if this is at the expense of reduced performance. In this context, the development of practical cooperative protocols will be facilitated by identifying the simplest possible abstractions of cooperative signaling strategies.

Objectives and Outline

This text reviews progress in cooperative communication networks. Our survey is by no means exhaustive. Instead, we assemble a representative sample of recent results to serve as a roadmap for the area. Our emphasis is on wireless networks, but many of the results apply to cooperation in wireline networks and mixed wireless/wireline networks. We intend our presentation to be a tutorial for the reader who is familiar with information theory concepts but has not actively followed the field. For the active researcher, we would like this contribution to serve as a useful digest of significant results.

We hope this text will encourage readers to find new ways to apply the fundamental ideas of network cooperation. We also hope we have made the area sufficiently accessible to network designers to contribute to the advancement of networking practice.

Topic 2 provides an overview of conventional communication and networking. This includes information-theoretic capacity definitions for the point-to-point links that are the traditional basis for networks, as well as key elements of the link and network layer protocols. While much or all of this material will be familiar to the reader, we include it to provide contrast to the cooperative networks that follow. Topics 3, 4, and 5 emphasize an information-theoretic treatment of the capacity of cooperative networks. In particular, topic 3 provides basic definitions, and a sampling of fundamental network models and corresponding capacity results. Topic 4 develops the key ideas in information-theoretic relaying and makes apparent how the methods go well beyond store-and-forward routing. Topic 5 focuses on time-varying wireless networks and how they can be made more reliable through the use of cooperative diversity mechanisms. Finally, topic 6 investigates implementation aspects of these cooperative strategies, concluding with a review of recent proposals in the literature for network cooperation protocols.