Project Links Logo Artwork
Graph Theory: Networking
Home > Graph Theory: Networking > Routing > Designing A Routing Protocol
Crib Sheet
Library
Help
Map
Problem List
Module Home
Links Home


conceptsdiscoverapplycollaboratepractice
 
 
go backgo forward
go backgo forward

Designing A Routing Protocol

Design Issues

The designer of a routing protocol needs to make a number of decisions concerning the features of the future network that best fit the particular specifications and available mechanisms. Often, the decision involves making a choice between two opposing features. Examples of such choices include:

  1. Centralized vs. distributed routing: Under a centralized routing protocol, a central processor collects information about the status of each link (up or down, its utilization and capacity) and processes this information to compute a routing table for each node. In distributed routing, the routers cooperate using a distributed routing protocol to create mutually-consistent routing tables.
  2. Source-based vs. hop-by-hop routing: In source-based routing, the header of the packet carries the entire route. In hop-by-hop routing, the header carries only the destination address; each router along the path chooses the next hop.
  3. These alternatives represent two extremes. Intermediate strategies, in which the header contains more than just the minimum (the destination address), but also specifies some of the whole path, are also used.
  4. Often, the question is: What is the best trade-off between routing specificity and the overhead incurred in control messages and the increased size of the packet's header?
  5. Deterministic vs. stochastic routing: A deterministic router forwards packets toward a destination node along exactly one path, which depends only on the address of the destination. A stochastic router maintains more than one next hop for each possible destination; it randomly picks one of the available hops when forwarding the packets.
  6. Dynamic vs. static routing: With dynamic routing, the choice of routes depends on parameters describing the current state of the network (for example, the workload of some of the links). Static (or state-independent) routing ignores the state of the network. Routes are selected on the basis of the network topology (for example, by selecting a shortest-length path). Telephone networks once were static, but state-dependent routing with multiple paths is now the norm. The Internet uses both static and dynamic routing.
 
 
go backgo forward
go backgo forward