Problem 6
1. The routing function attempts to find the least-cost route through the network, with cost based on number of hops, expected delay, or other metrics 2. Adaptive routing algorithms typically rely on the exchange of information about traffic conditions among nodes. 3. Routing decisions are made on the basis of some performance criterion.Two key characteristics of the decision are the time and place that the decision is made. 4. Decision time is determined by whether the routing decision is made on a packet or virtual circuit basis. When the internal operation of the network is datagram, a routing decision is made individually for each packet. For internal virtual circuit operation, a routing decision is made at the time the virtual circuit is established. 5. The term decision place refers to which node or nodes in the network are responsible for the routing decision. For distributed routing, in which each node has the responsibility of selecting an output link for routing packets as they arrive. For centralized routing, the decision is made by some designated node,such as a network control center. 6. The routing algorithm is that part of the network layer software responsible for deciding which output line an incoming packet should be transmitted on.
7. A router has two processes inside it. One of them handles each packet as it arrives, looking up the outgoing line to use for it in the routing tables. This process is forwarding. The other process is responsible for filling in and updating the routing tables. That is where the routing algorithm comes into play.
8. Nonadaptive algorithms do not base their routing decisions on measurements or estimates of the current traffic and topology. Instead, the choice of the route to use is computed in advance, off-line, and downloaded to the routers when the network is booted. This procedure is sometimes called static routing. 9. Adaptive algorithms, change their routing decisions to reflect changes in the topology, and usually the traffic as well.
10. Flooding is the technique requires no network information whatsoever and works as follows. A packet is sent by a source node to every one of its neighbors. At each node, an incoming packet is retransmitted on all outgoing links except for the link on which it arrived.
11. Dijkstra's algorithm is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge path costs, producing a shortest path tree. The shortest path algorithm is widely used in network routing protocols, most notably IS-IS and OSPF (Open Shortest Path First).
12. The Bellman-Ford algorithm can be stated as follows: Find the shortest paths from a given source node subject to the constraint that the paths contain at most one link, then find the shortest paths with a constraint of paths of at most two links, and so on.
13. The routers in an internet are responsible for receiving and forwarding packets through the interconnected set of networks. Each router makes routing decision based on knowledge of the topology and traffic/delay conditions of the internet. 14. Routing information is Information about the topology and delays of the internet. Routing algorithmis The algorithm used to make a routing decision for a particular datagram, based on current routing information.
15. An AS is a set of routers and networks managed by a single organization. An AS consists of a group of routers exchanging information via a common routing protocol. 16. Interior router protocol (IRP) is used to pass routing information between routers within an AS. Exterior router protocol (ERP) is used to pass routing information between routers in different Ass.
17. Within an autonomous system, IGP software uses a routing metric to choose an optimal path each destination. EGP software finds a path each destination, but cannot find an optimal path because it cannot compare routing metrics from multiple autonomous systems.
18. Internet routing protocols employ one of three approaches to gathering and using routing information: distance-vector routing, link-state routing, and path-vector routing. 19. Distance-vector routing requires that each node (router or host that implements the routing protocol) exchange information with its neighboring nodes. Two nodes are said to be neighbors if they are both directly connected to the same network. The first generation routing algorithm for ARPANET uses this approach.
20. Path-vector routing, is to dispense with routing metrics and simply provide information about which networks can be reached by a given router and the ASs that must be crossed to get there.
21. Link-state routing is designed to overcome the drawbacks of distance-vector routing.When a router is initialized, it determines the link cost on each of its network interfaces.The router then advertises this set of link costs to all other routers in the internet topology, not just neighboring routers. Because the router has a representation of the entire network, it does not use a distributed version of a routing algorithm, as is done in distance-vector routing. Rather, the router can use any routing algorithm to determine the shortest paths. In practice, Dijkstra’s algorithm is used. The Open Shortest Path First (OSPF) is an example of a routing protocol that uses link-state routing.
22. The Border Gateway Protocol (BGP) was developed for use in conjunction with internets that employ the TCP/IP suite, although the concepts are applicable to any internet. BGP has become the preferred exterior router protocol for the Internet.