Network routing tools and techniques

Network routing tools and techniques

54.1 Purpose

This chapter focuses on several common network routing techniques (generally, location connectivity analysis). The major objectives of these routing techniques include controlling network data flow, determining the status of the sending and the receiving nodes, identifying the best (sometimes optimal) route to transmit data, reducing transmission delays and related errors, and preventing the overuse of a particular route or node.

Network design is a highly specialized discipline, and a detailed explanation of location connectivity analysis tools and techniques is beyond the scope of this book. This chapter is written for systems analysts and information system consultants who must work with network specialists.

54.2 Strengths, weaknesses, and limitations

The techniques described in this chapter are used to estimate and/or predict data flows and minimize data congestion in a distributed information system. Using these techniques can help reduce transmission problems owing to the speed and capacity constraints imposed by the transmission media.

It is difficult to measure the highway effect or to match users needs with emerging computing technology using these techniques. Also, the techniques described in this chapter do not always yield the best route for data transmission.

54.3 Inputs and related ideas

Network topologies are discussed in Chapter 52. Network analysis is covered in Chapter 53. The need for a network is established during the analysis (Part IV) and high-level design (Part V) stages of the system development life cycle. Key network design parameters are documented in the requirements specifications (Chapter 35).

54.4 Concepts

A network consists of a set of nodes (computers, routers, etc.) linked by communication lines. When a source node transmits a message, there are typically several possible paths the message can take from node to node through the network to reach its destination. The specific path selected for a given message is called a route. Location connectivity analysis is used to control network data flow, determine the status of the sending and receiving nodes, identify the best (or optimal) route, reduce transmission delays and related errors, and prevent the overuse of a particular route or node. This chapter focuses on several common routing techniques.

54.4.1 Centralized routing

Centralized routing is used when the distributed network is centrally controlled. The basic idea is to provide the central node with super-authority over all the other nodes. The network routing software installed on the central node can be used to overview the operation of the entire network, locate bottlenecks and underutilized nodes, calculate and recompute the optimal path between a sending node and a receiving node, and adjust the routing path by constructing a new routing table.

Centralized routing provides centralized control, integrated supervision of the network, very good security, and excellent back-up control. The central node is relatively expensive to operate and maintain, however, and the entire network goes down if the central node fails. Some operating inefficiency is possible because the central node must perform all routing calculations. Also, the calculated optimal paths may not reflect the current status of the network if they are based on (even seconds old) historical network information.

54.4.2 Distributed routing

Distributed routing relies on each node to compute its own routing table and build the required connections with its neighbors. Ideally, the network operation, status, and architecture of each node is transparent. Distributed routing is more flexible than centralized routing because each node handles its own routing. The result is often improved system performance.

54.4.2.1 Static routing

Static routing establishes routine paths between sending and receiving nodes based on a data flow analysis of historical data. With static routing, the path is selected from a predefined table, so there is no need to readjust paths or compute the next node. However, if the established link between any pair of nodes fails, static routing cannot adjust. Also, as transmission patterns change, static routing patterns can quickly become inefficient.

Fixed routing always utilizes a predetermined fixed route when transmitting between a specific pair of nodes. Fixed routing is widely used in mesh topology networks, particularly when reliability and security are primary objectives.

With weighted routing, different routing paths are selected for each message based on a predetermined desirable utilization rate. For example, imagine that there are three paths (via node A, B, or C) between the source node and the destination node (Figure 54.1). The objective is to transmit 50 percent of all messages via node A, 30 percent via node B, and the remaining 20 percent via node C. The source node uses a random number generator to select the route based on the predetermined probabilities.

54.4.2.2 Adaptive routing

Adaptive routing, also called dynamic routing, selects the best route based on such criteria as the speed, capacity, or cost of the link, the utilization rate of a particular node, the failure rate of a particular path, the type of data to be transmitted, response time, throughput, and so on. Often, a prioritized list of decision criteria (called a portfolio) is used.

The objective of the quickest route algorithm is to send the message to the next available neighboring node (other than the sending node) as quickly as possible. The advantage is fast transmission, but there is no guarantee that the node selected will be closer to the destination. In some cases, the quickest route algorithm can increase the time required to deliver a message.

Figure 54.1  Weighted routing.

The best route algorithm uses such parameters as the type of message, the rate of under-utilization or over-utilization of a particular node, and the number of intermediate nodes between the source and the destination. Such tools as linear programming, goal programming, and similar management science techniques can be used to select and rank the different routing alternatives based on the established criteria.

54.4.2.3 Broadcast routing

With broadcast routing, a header containing the address of the receiving node is added to the message. The message is then transmitted to all the nodes in the network, and the node whose address matches the header reacts to the message. Note that each node must have a list of addresses of all the nodes in the network. Security is a major concern because every node receives a copy of the message. Broadcast routing is popular in collision detection networks.

54.5 Key terms

Adaptive routing —

A distributed routing technique that selects the best route based on such criteria as the speed, capacity, or cost of the link, the utilization rate of a particular node, the failure rate of a particular path, the type of data transmitted, response time, throughput, and so on; also known as dynamic routing.

Best route algorithm —

An adaptive routing technique that uses such parameters as the type of message, the rate of under-utilization or over-utilization of a particular node, and the number of intermediate nodes between the source and the destination.

Bottleneck (choke point) —

A place (usually, a node or a path) in the network where message flow exceeds capacity, resulting in delays, and even lost messages.

Broadcast routing —

A routing technique in which a header containing the address of the receiving node is added to the message; the message is then transmitted to all the nodes in the network, and the node whose address matches the header reacts to the message.

Centralized routing —

A routing technique in which the central node has super-authority over all the other nodes.

Collision detection —

A network management technique in which the nodes are allowed to transmit at any time; if two messages collide, the collision is sensed and the messages are retransmitted.

Distributed database —

A database with different subsets of data distributed among several sites that are connected by a network.

Distributed routing —

A routing technique that relies on each node to compute its own routing table and build the required connections with its neighbors.

Fixed routing —

A static routing technique that always utilizes a predetermined fixed route when transmitting between a specific pair of nodes.

Highway effect (turnpike effect) —

The tendency of users to quickly adopt new technology as soon as it proves its usefulness; because of the highway effect, the demands placed on a system often exceed projections. This term was initially coined in the 1950s when the traffic load on the Pennsylvania Turnpike exceeded the designers’ long-term, worst-case projections soon after the road opened.

Location connectivity analysis —

A network and distributed database design technique used to help control network data flow, determine the status of the sending and receiving nodes, identify the best route to transmit data, reduce transmission delays and related errors, and prevent the overuse of a particular route or node; also known as connectivity analysis or routing analysis.

Network —

Two or more computers linked by a communication line.

Node —

A connection point (computer, workstation, peripheral, concentrator, etc.) in a network.

Path —

A group of connected links that allow the transmission of information from a source to destination(s).

Portfolio —

A prioritized list of routing decision criteria.

Protocol —

A set of rules that governs data communication.

Quickest route algorithm —

An adaptive routing technique that sends the message to the next available neighboring node (other than the sending node) as quickly as possible.

Route —

The path(s) or subset used to actually transmit information from a source to a destination(s).

Router —

An intelligent device that provides network connections and performs such services as protocol conversion and message routing.

Routing —

The process of determining the best available path (or path segment) to transmit a message.

Static routing —

A distributed routing technique that establishes routine paths between sending and receiving nodes based on a data flow analysis of historical data.

Token passing —

A network management technique in which an electronic token is passed continuously from node to node (following the direction of flow) around the network and a given node can transmit a message only when it holds the token.

Topology —

A physical arrangement of the nodes and connections in a network.

Weighted routing —

A static routing technique in which different routing paths are selected for each message based on a predetermined desirable utilization rate.

54.6 Software

Not applicable.

54.7 References

1.  Conrad, J. W., Handbook of Communications Systems Management, Auerbach, Boston, MA, 1988, 1989, 1990–1991.

2.  Fitzgerald, J. and Dennis, A., Business Data Communications and Networking, John Wiley & Sons, New York, 1996.

3.  Martin, J. and Leben, J., Principle of Data Communications, Prentice-Hall, Englewood Cliffs, NJ, 1988.

4.  Martin, J. and Leben, J., Data Communications Technology, Prentice-Hall, Englewood Cliffs, NJ, 1988.

5.  Ramos, E., Schroeder, A., and Beheler A., Computer Networking Concepts, Prentice-Hall, Englewood Cliffs, NJ, 1996.

6.  Rhodes, P. D., Building a Network: How to Specify, Design, Procure, and Install a Corporate LAN, McGraw-Hill, New York, 1995.

7.  Slone, J. P. and Drinan, A., Handbook of Local Area Networks, Auerbach, Boston, MA, 1991.

8.  Spohn, D. L., Data Network Design, McGraw-Hill, New York, 1997.

9.  Stallings, W., Business Data Communications, Macmillan, New York, 1990.

10.  Stallings, W., Handbook of Computer-Communications Standards: Local Network Standards, vol. 2, Macmillan, New York, 1987.

11.  Taylor, D. E., The McGraw-Hill Internetworking Handbook, McGraw-Hill, New York, 1995.