Chapter 13 Communication Networks 13.1 Communication Networks Modeling communication networks is an important application of digraphs in computer science. In this such models, vertices represent computers, processors, and switches; edges will represent wires, fiber, or other transmission lines through which data flows. For some communication networks, like the internet, the corre-sponding graph is enormous and largely chaotic. Highly structured networks, by contrast, find application in telephone switching systems and the communication hardware inside parallel computers. In this chapter, we’ll look at some of the nicest and most commonly used structured networks. 13.2 Complete Binary Tree Let’s start with a complete binary tree. Here is an example with 4 inputs and 4 outputs. 253254 CHAPTER 13. COMMUNICATION NETWORKS IN OUT IN IN INOUT OUT OUT0 0 1 1 2 2 3 3The kinds of communication networks we consider aim to transmit packets of data between computers, processors, telephones, or other devices. The term packet refers to some roughly fixed-size quantity of data— 256 bytes or 4096 bytes or whatever. In this diagram and many that follow, the squares represent terminals, sources and destinations for packets of data. The circles represent switches, which direct packets through the network. A switch receives packets on incoming edges and relays them forward along the outgoing edges. Thus, you can imagine a data packet hopping through the network from an input terminal, through a sequence of switches joined by directed edges, to an output terminal. Recall that there is a unique simple path between every pair of vertices in a tree. So the natural way to route a packet of data from an input terminal to an output in the complete binary tree is along the corresponding directed path. For example, the route of a packet traveling from input 1 to output 3 is shown in bold. 13.3 Routing Problems Communication networks are supposed to get packets from inputs to outputs, with each packet entering the network at its own input switch and arriving at its own output switch. We’re going to consider several different communication net-work designs, where each network has N inputs and N outputs; for convenience, we’ll assume N is a power of two. Which input is supposed to go where is specified by a permutation of {0, 1, . . . , N − 1}. So a permutation, π, defines a routing problem: get a packet that starts at input i to output π(i). A routing, P , that solves a routing problem, π, is a set of paths from each input to its specified output. That is, P is a set of n paths, Pi, for i = 0 . . . , N − 1, where Pi goes from input i to output π(i).255 13.4. NETWORK DIAMETER 13.4 Network Diameter The delay between the time that a packets arrives at an input and arrives at its designated output is a critical issue in communication networks. Generally this delay is proportional to the length of the path a packet follows. Assuming it takes one time unit to travel across a wire, the delay of a packet will be the number of wires it crosses going from input to output. Generally packets are routed to go from input to output by the shortest path possible. With a shortest path routing, the worst case delay is the distance be-tween the input and output that are farthest apart. This is called the diameter of the network. In other words, the diameter of a network1 is the maximum length of any shortest path between an input and an output. For example, in the complete binary tree above, the distance from input 1 to output 3 is six. No input and output are farther apart than this, so the diameter of this tree is also six. More generally, the diameter of a complete binary tree with N inputs and out-puts is 2 log N +2. (All logarithms in this lecture— and in most of computer science —are base 2.) This is quite good, because the logarithm function grows very slowly. We could connect up 210 = 1024 inputs and outputs using a complete binary tree and the worst input-output delay for any packet would be this diameter, namely, 2 log(210) + 2 = 22. 13.4.1 Switch Size One way to reduce the diameter of a network is to use larger switches. For exam-ple, in the complete binary tree, most of the switches have three incoming edges and three outgoing edges, which makes them 3 × 3 switches. If we had 4 × 4 switches, then we could construct a complete ternary tree with an even smaller di-ameter. In principle, we could even connect up all the inputs and outputs via a single monster N × N switch. This isn’t very productive, however, since we’ve just concealed the original net-work design problem inside this abstract switch. Eventually, we’ll have to design the internals of the monster switch using simpler components, and then we’re right back where we started. So the challenge in designing a communication network is figuring out how to get the functionality of an N × N switch using fixed size, elementary devices, like 3 × 3 switches. 13.5 Switch Count Another goal in designing a communication network is to use as few switches as possible. The number of switches in a complete binary tree is 1+2+4+ 8+ +N,···since there is 1 switch at the top (the “root switch”), 2 below it, 4 below those, and 1The usual definition of diameter for a general graph (simple or directed) is the largest distance be-tween any two vertices, but in the context of a communication network we’re only interested in the distance between inputs and outputs, not between arbitrary pairs of vertices.256 CHAPTER 13. COMMUNICATION NETWORKS so forth. By the formula (6.5) for geometric sums, the total number of switches is 2N − 1, which is nearly the best possible with 3 × 3 switches. 13.6 Network Latency We’ll sometimes be choosing routings through a network that optimize some quan-tity besides delay. For example, in the next section we’ll be trying to minimize packet congestion. When we’re not minimizing delay, shortest routings are not al-ways the best, and in general, the delay of a packet will depend on how it is routed. For any routing, the most delayed packet will be the one that follows the longest path in the routing. The length of the longest path in a routing is called its latency. The latency of a network depends on what’s being optimized. It is measured by assuming that optimal routings are always
View Full Document
Unlocking...