Table of Contents
| Preface | |
| Ch. 1 | Introduction | 1 |
| Ch. 2 | "Hello World" of Network Design | 11 |
| Ch. 3 | Graphs, Trees, and Tours | 49 |
| Ch. 4 | Traffic and Cost Generators | 97 |
| Ch. 5 | Access Network Design | 145 |
| Ch. 6 | Multispeed Access Designs | 181 |
| Ch. 7 | Multicenter Local-Access Design | 195 |
| Ch. 8 | Mesh Network Design | 205 |
| Ch. 9 | Mesh Network Design-II | 267 |
| Ch. 10 | Network Design with Constraints | 279 |
| Ch. 11 | Network Redesign | 337 |
| Ch. 12 | Closing Words | 385 |
| App. A | Generating Sites in Squareworld | 389 |
| App. B | Computing Creditability of Simple Nearest Neighbor | 391 |
| App. C | 10 Minutes of Set Theory | 399 |
| App. D | The EQUIPMENT Table | 403 |
| App. E | Trace of the Esau-Williams Algorithm | 407 |
| App. F | Code Listings | 413 |
| App. G | The Design Tool Delite | 417 |
| Glossary | 419 |
| Bibliography | 425 |
| Index | 429 |
Read an Excerpt
Chapter 10: Network Design with Constraints
Overview
In the previous chapters we have designed access networks and backbone networks. Often the algorithms push us toward a certain type of design as being the cheapest that solves a particular problem. Sometimes that design is unacceptable to the network owner. There are then additional constraints imposed upon the designer. This is where the art of network design comes into play. The constraints we encounter are not general or generalizable. They simply reflect some business plan that requires that the "natural" best network be rejected in favor of another kind of network.
To understand this problem we will give some examples. First, suppose we have a design problem involving 50 large United States cities. We must design a network that carries the traffic and that has 2 edge-disjoint paths between Chicago and Dallas and 3 edge-disjoint paths between New York and Los Angeles. How do we create such a design?
A network is to be built connecting 75 stores to a corporate headquarters. Each store generates about 500 bps of traffic and receives about 1500 bps of traffic. Clearly, an MST or CMST will be the correct solution but you are told that each store needs 64 Kbps access and that the traffic to each store can take at most 3 hops. Further, frame relay cannot be considered due to the lack of availability in 18 different sites. How do you design a network?
There can be a number of different problems that are simple to state but challenging to solve. How do we get the lowest-cost network where the average end-to-end delay is 300 ms or less? How do we get the most attractive network where the probability thatthe network will disconnect is less than 0.9999?
A more complex problem is the following. We need to design a network with high-security nodes and low-security nodes. Any 2 high-security nodes must have a path between them that doesn't pass through a lowsecurity node. Clearly we can build 2 separate networks but can we do better?
Going further, how do we create a MUX design that routes all the traffic In the event of the failure of any backbone link? The wrinkle here is that in addition to the regular point-to-point traffic, the network must support 2 multicasts, I from New York and 1 from Chicago to all other nodes to bring in financial market updates.
Suppose that as an economy measure we are asked to design a network using routers that are left over from a previous network. These routers can handle 10,000 datagrams/second but can only terminate 4 links. Each link is limited to be T1. Unfortunately, there are 8.5 Mbps of traffic from Atlanta to the rest of the network. How do we configure the routers to handle this traffic?
All of these problems except, possibly, designing for single failures are problems that need to be attacked by either manual design or writing problem-specific code. Problem- specific code is the disposable munition of network design-you write it, you use it, you throw it away. Of course if the code turns out, in practice, to be used again and again it will eventually be, promoted to the status of a tool. Any real network problem, however, inevitably will involve adapting to the specifics of constraints at hand. In that regard, network design is more like the bespoke tailoring of Savile Row than buying a suit off the rack at Macy's. There is a good deal of handwork and deft little touches with the needle that are necessary to do a really good job. Certainly these special constraints are what justify spending the time to really understand the algorithms. Only by having a thorough understanding of their operation can we modify them to do what we wish.
From the other side, if you are setting requirements for network designs you should do so with a clear understanding that every additional constraint placed on a design makes a hard job harder and an expensive job even more expensive. If you are too aggressive in adding constraints, you will make the problem insoluble.
10. 1 War Story
My colleagues and I were once given the problem of interconnecting a set of cities for a high-capacity backbone. For political reasons it was decided that every node needed to have exactly 3 links connecting it to other nodes so that no site appeared to be more important than other sites. While I could never prove that the problem had no solution, I was unable to find an answer and I had to report back that the only designs we could produce did indeed have some sites with more than 3 links.
There is no dishonor in reporting back that you couldn't meet all the constraints in a design unless someone else solves the problem with a fraction of the effort that you have expended.
10.1.1 Families of Constraints
One way of thinking about the constraints is to try to divide them into families. The following categories are useful and are each discussed separately in subsequent sections of this chapter:
- Hop constraints. These can be further refined as worst-case constraints, average hop constraints, and node-pair constraints.
- Equipment constraints. These can be further refined as degree constraints and throughput constraints.
- Link constraints. These are usually either required links or forbidden links. Performance constraints. These can be further divided into node-pair constraints, average performance constraints, and worst-case constraints.
- Reliability constraints. These include node-pair reliability, backbone reliability, and entire network reliability.
- Miscellaneous constraints. These are defined as anything else or anything new. The problem with high-security and low-security nodes is an example. . . .
loading...