In today lesson we will discuss routing in packet networks. The figure shows a packet switch network providing communication services among multiple nodes. For example, from node 1 to node 6 there are three possible loop of free routes. 1-3-6, 1-4-5-6, and 1-2-5-6, which path is the best one? The optimality depends on the objective function that the network tries to optimize, for example, minimal delay, minimal number of hops, maximum bandwidth, and the minimum cost. Please note that node here actually is the router. In general, a routing algorithm should seek one or more goals, such as rapid and aggregate delivery of packets, adaptability to change, robustness, and low overhead. Once the routing algorithm has determined the set or path, the path information is stored in the routing table. So that each router knows how to forward package. The specific route information stored depends on the type of packet switching. But in general, creating a routing table, need information on state of links, need to distribute links state information, and compute optimal routes based on link state information. The figure shows a routing table for our datagram network. Each table contains an entry for each passport destination in the network. Each entry specifies the next hop that is to be taken by packets with associated destination. When a packet arrives, route is the terminal by table lookup. The problem is when the number of destinations become very large, the size of the routing table may exceed the practical implementation limit. For example, Internet protocol, IP, use datagram packet switching across networks. Each host has two part IP address; network address plus host address. Routers do table lookup based on network address only which will reduce size of routing tables significantly. Network addresses can be assigned so that they can also be aggregated which can further reduce our routing table size. In a virtual-circuit a packet switch network route is determined during connection setup. The virtual connection identifier, VCI, is local to the router and each link the identifier may be translated to a different identifier by label switching depending on the variable VCIs at a given link. The size of rod and cables can be reduced if a hierarchical approach is used in assignment of address. If the address is non-hierarchical as shown in the figure there is no relationship between address and routing proximity. So routers need to maintain 16 inches in their routing table, but in this figure the host and each of the four sides have the same prefix denoted here by the first two pits of the address. Therefore, the two routers need only to maintain tables with the four entries each. Essentially, host that are near each other should have address that have common prefix. In this way, routers need to exam only part of the address, the prefix, in order to decide how a package should be routed. Next, we exam two specialized approach to routing called flooding and deflection routing, which use certain network scenarios. Flooding very useful in the studying of networks, and the propagation of information to all nodes. The principle calls for a packet switch to forward an incoming packet to all ports except as the one, the packet it wasn't received from. Flooding is an effective routing approach when the information in the routing table is not available, such as during system set up. But the problem is the flooding may easily swamp the network as one packet creates multiple packets that in turn create multiples of multiple packets. Generating packets in an exponentially growth rate. The next few view graphs illustrate the exponential growth in number of packets generated during flooding. To reduce resource consumption due to flooding, one simple method is to use a Time-to-Live field in each packet that it limits the number of hops to a certain diameter. Each router decrements the time to live by one before flooding the pocket. If the value reaches zero, the router discards the pocket. Another approach each router has is identifier before flooding. And discarded the packet if it contains the same identifier of the router. Furthermore, sequence number can be used for ease of implementation. Deflection routing requires the network to provide a multiple pass for each source and destination pair. One advantage is that is a node can be bufferless. Since packets don't have to wait for a specific port to become available. If the preferred port is unavailable, the packet can be deflected to another port which it will eventually find its own way to the destination. Deflection routing often works well in a regular topology. One example of regular topology is called a Manhattan Street Network. In this lesson, we learn three key points. First, routing algorithm optimality depends on the objective function that the network operator tries to optimize. Second, hierarchical addressing reduces the size of routing table. And finally, flooding is very useful when routing tables are unavailable.
