USA: +1(669)289-8683 
Sign in
PLEASE SEE ATTACHED!!
Areas of interest Network topology and Network nodes
Please leave detailed explanations.
1) Consider the following network topology:
Assume the original routing table in D is as below.
Now suppose that D receives from A the following advertisement:
Will the table in D change? If so how?
2) Consider the following network. With the indicated link costs, use Dijkstra’s shortest-path algorithm to compute the shortest path from z to all network nodes.
Show how the algorithm works by computing a table similar to the following table:
Forwarding and Routing
The role of the network layer is thus deceptively simple— to move packets from a sending host to a receiving host. To do so, two important network- layer functions can be identified:
• Forwarding.
W
hen a packet arrives at a router’s input link, the router must move the packet to the appropriate output link. For example, a packet arriving from Host H1 to Router R1 must be forwarded to the next router on a path to H2. In Section 4.3, we’ll look inside a router and examine how a packet is actually for-warded from an input link to an output link within a router.
• Routing. The network layer must determine the route or path taken by packets as they flow from a sender to a receiver. The algorithms that calculate these paths are referred to as routing algorithms. A routing algorithm would determine, for example, the path along which packets flow from H1 to H2.
The terms forwarding and routing are often used interchangeably by authors dis-cussing the network layer. We’ll use these terms much more precisely in this book. Forwarding refers to the router- local action of transferring a packet from an input link interface to the appropriate output link interface. Routing refers to the network- wide process that determines the end- to- end paths that packets take from source to destina-tion.
U
sing a driving analogy, consider the trip from Pennsylvania to Florida under-taken by our traveler back in Section 1.3.1. During this trip, our driver passes through many interchanges en route to Florida. We can think of forwarding as the process of getting through a single interchange: A car enters the interchange from one road and determines which road it should take to leave the interchange. We can think of routing as the process of planning the trip from Pennsylvania to Florida: Before embarking on the trip, the driver has consulted a map and chosen one of many paths possible, with each path consisting of a series of road segments connected at interchanges.
Every router has a forwarding table. A router forwards a packet by examin-ing the value of a field in the arriving packet’s header, and then using this header value to index into the router’s forwarding table. The value stored in the forward-ing table entry for that header indicates the router’s outgoing link interface to which that packet is to be forwarded. Depending on the network- layer protocol, the header value could be the destination address of the packet or an indication of the connection to which the packet belongs. Figure 4.2 provides an example. In Figure 4.2, a packet with a header field value of 0111 arrives to a router. The router indexes into its forwarding table and determines that the output link interface for this packet is interface 2. The router then internally forwards the packet to interface 2. In Section 4.3, we’ll look inside a router and examine the forwarding function in much greater detail.
Y
ou might now be wondering how the forwarding tables in the routers are con-figured. This is a crucial issue, one that exposes the important interplay between routing and forwarding. As shown in Figure 4.2, the routing algorithm determines the values that are inserted into the routers’ forwarding tables. The routing algorithm may be centralized ( e. g., with an algorithm executing on a central site and down-loading routing information to each of the routers) or decentralized ( i. e., with a piece of the distributed routing algorithm running in each router). In either case, a router receives routing protocol messages, which are used to configure its forward-ing table. The distinct and different purposes of the forwarding and routing func-tions can be further illustrated by considering the hypothetical ( and unrealistic, but technically feasible) case of a network in which all forwarding tables are configured directly by human network operators physically present at the routers. In this case, no routing protocols would be required! Of course, the human operators would need to interact with each other to ensure that the forwarding tables were configured in such a way that packets reached their intended destinations. It’s also likely that human configuration would be more error- prone and much slower to respond to changes in the network topology than a routing protocol. We’re thus fortunate that all networks have both a forwarding and a routing function!
While we’re on the topic of terminology, it’s worth mentioning two other terms that are often used interchangeably, but that we will use more carefully. We’ll reserve the term packet switch to mean a general packet- switching device that transfers a packet from input link interface to output link interface, according to the value in a field in the header of the packet. Some packet switches, called link- layer switches ( exam-ined in Chapter 5), base their forwarding decision on values in the fields of the link-layer frame; switches are thus referred to as link- layer ( layer 2) devices. Other packet switches, called routers, base their forwarding decision on the value in the network-layer field. Routers are thus network- layer ( layer 3) devices, but must also implement layer 2 protocols as well, since layer 3 devices require the services of layer 2 to imple-ment their ( layer 3) functionality. ( To fully appreciate this important distinction, you might want to review Section 1.5.2, where we discuss network- layer datagrams and link- layer frames and their relationship.) To confuse matters, marketing literature often refers to “ layer 3 switches” for routers with Ethernet interfaces, but these are really layer 3 devices. Since our focus in this chapter is on the network layer, we use the term router in place of packet switch. We’ll even use the term router when talking about packet switches in virtual- circuit networks ( soon to be discussed).
Routing Algorithms
So far in this chapter, we’ve mostly explored the network layer’s forwarding func-tion. We learned that when a packet arrives to a router, the router indexes a forward-ing table and determines the link interface to which the packet is to be directed. We also learned that routing algorithms, operating in network routers, exchange and compute the information that is used to configure these forwarding tables. The inter-play between routing algorithms and forwarding tables was shown in Figure 4.2. Having explored forwarding in some depth we now turn our attention to the other major topic of this chapter, namely, the network layer’s critical routing function. Whether the network layer provides a datagram service ( in which case different pack-ets between a given source- destination pair may take different routes) or a
V
C serv-ice ( in which case all packets between a given source and destination will take the same path), the network layer must nonetheless determine the path that packets take from senders to receivers. We’ll see that the job of routing is to determine good paths ( equivalently, routes), from senders to receivers, through the network of routers.
Typically a host is attached directly to one router, the default router for the host ( also called the first- hop router for the host). Whenever a host sends a packet, the packet is transferred to its default router. We refer to the default router of the source host as the source router and the default router of the destination host as the destination router. The problem of routing a packet from source host to destination host clearly boils down to the problem of routing the packet from source router to destination router, which is the focus of this section.
The purpose of a routing algorithm is then simple: given a set of routers, with links connecting the routers, a routing algorithm finds a “ good” path from source router to destination router. Typically, a good path is one that has the least cost. We’ll see, however, that in practice, real- world concerns such as policy issues ( for example, a rule such as “ router x, belonging to organization Y, should not forward any packets originating from the network owned by organization
Z
”) also come into play to complicate the conceptually simple and elegant algorithms whose theory underlies the practice of routing in today’s networks.
A graph is used to formulate routing problems. Recall that a graph G = ( N, E) is a set N of nodes and a collection E of edges, where each edge is a pair of nodes from N. In the context of network- layer routing, the nodes in the graph represent routers— the points at which packet- forwarding decisions are made— and the edges connecting these nodes represent the physical links between these routers. Such a graph abstraction of a computer network is shown in Figure 4.27. To view some graphs representing real network maps, see [ Dodge 2012, Cheswick 2000]; for a discussion of how well different graph- based models model the Internet, see [ Zegura 1997, Faloutsos 1999, Li 2004].
As shown in Figure 4.27, an edge also has a value representing its cost. Typi-cally, an edge’s cost may reflect the physical length of the corresponding link ( for example, a transoceanic link might have a higher cost than a short- haul terrestrial link), the link speed, or the monetary cost associated with a link. For our purposes, we’ll simply take the edge costs as a given and won’t worry about how they are determined. For any edge ( x, y) in E, we denote c( x, y) as the cost of the edge between nodes x and y. If the pair ( x, y) does not belong to E, we set c( x, y) = 8. Also, through-out we consider only undirected graphs ( i. e., graphs whose edges do not have a direction), so that edge ( x, y) is the same as edge ( y, x) and that c( x, y) = c( y, x). Also, a node y is said to be a neighbor of node x if ( x, y) belongs to E.
5
3
Z
U
Y
X
V
W
2 5 2 3 1 1 2 1
Figure 4.27 Abstract graph model of a computer network
Given that costs are assigned to the various edges in the graph abstraction, a natu-ral goal of a routing algorithm is to identify the least costly paths between sources and destinations. To make this problem more precise, recall that a path in a graph G = ( N, E) is a sequence of nodes ( x 1 , x 2 ,…, x p ) such that each of the pairs ( x 1 , x 2 ), ( x 2 , x 3 ),…,( x p- 1 , x p ) are edges in E. The cost of a path ( x 1 , x 2 ,…, x p ) is simply the sum of all the edge costs along the path, that is, c( x 1 , x 2 ) + c( x 2 , x 3 ) + …+ c( x p- 1 , x p ). Given any two nodes x and y, there are typically many paths between the two nodes, with each path having a cost. One or more of these paths is a least- cost path. The least- cost problem is therefore clear: Find a path between the source and destination that has least cost. In Figure 4.27, for example, the least- cost path between source node u and destination node w is ( u, x, y, w) with a path cost of 3. Note that if all edges in the graph have the same cost, the least- cost path is also the shortest path ( that is, the path with the smallest number of links between the source and the destination).
As a simple exercise, try finding the least- cost path from node u to z in Figure 4.27 and reflect for a moment on how you calculated that path. If you are like most people, you found the path from u to z by examining Figure 4.27, tracing a few routes from u to z, and somehow convincing yourself that the path you had chosen had the least cost among all possible paths. ( Did you check all of the 17 possible paths between u and z? Probably not!) Such a calculation is an example of a centralized routing algorithm— the routing algorithm was run in one location, your brain, with complete information about the network. Broadly, one way in which we can classify routing algorithms is according to whether they are global or decentralized.
• A global routing algorithm computes the least- cost path between a source and destination using complete, global knowledge about the network. That is, the algorithm takes the connectivity between all nodes and all link costs as inputs. This then requires that the algorithm somehow obtain this information before actually performing the calculation. The calculation itself can be run at one site (a centralized global routing algorithm) or replicated at multiple sites. The key distinguishing feature here, however, is that a global algorithm has complete information about connectivity and link costs. In practice, algorithms with global state information are often referred to as link- state ( LS) algorithms, since the algorithm must be aware of the cost of each link in the network. We’ll study LS algorithms in Section 4.5.1.
• In a decentralized routing algorithm, the calculation of the least- cost path is carried out in an iterative, distributed manner. No node has complete information about the costs of all network links. Instead, each node begins with only the knowledge of the costs of its own directly attached links. Then, through an itera-tive process of calculation and exchange of information with its neighboring nodes ( that is, nodes that are at the other end of links to which it itself is attached), a node gradually calculates the least- cost path to a destination or set of destinations. The decentralized routing algorithm we’ll study below in Section 4.5.2 is called a distance- vector ( DV) algorithm, because each node maintains a vector of estimates of the costs ( distances) to all other nodes in the network.
A second broad way to classify routing algorithms is according to whether they are static or dynamic. In static routing algorithms, routes change very slowly over time, often as a result of human intervention ( for example, a human manually edit-ing a router’s forwarding table). Dynamic routing algorithms change the routing paths as the network traffic loads or topology change. A dynamic algorithm can be run either periodically or in direct response to topology or link cost changes. While dynamic algorithms are more responsive to network changes, they are also more susceptible to problems such as routing loops and oscillation in routes.
Athird way to classify routing algorithms is according to whether they are load-sensitive or load- insensitive. In a load- sensitive algorithm, link costs vary dynami-cally to reflect the current level of congestion in the underlying link. If a high cost is associated with a link that is currently congested, a routing algorithm will tend to choose routes around such a congested link. While early ARPAnet routing algo-rithms were load- sensitive [ McQuillan 1980], a number of difficulties were encoun-tered [ Huitema 1998]. Today’s Internet routing algorithms ( such as RIP, OSPF, and BGP) are load- insensitive, as a link’s cost does not explicitly reflect its current ( or recent past) level of congestion.
4.5.1 The Link- State ( LS) Routing Algorithm
Recall that in a link- state algorithm, the network topology and all link costs are known, that is, available as input to the LS algorithm. In practice this is accom-plished by having each node broadcast link- state packets to all other nodes in the network, with each link- state packet containing the identities and costs of its attached links. In practice ( for example, with the Internet’s OSPF routing protocol, discussed in Section 4.6.1) this is often accomplished by a link- state broadcast algorithm [ Perlman 1999]. We’ll cover broadcast algorithms in Section 4.7. The result of the nodes’ broadcast is that all nodes have an identical and complete view of the network. Each node can then run the LS algorithm and compute the same set of least- cost paths as every other node.
The link- state routing algorithm we present below is known as Dijkstra’s algo-rithm, named after its inventor. A closely related algorithm is Prim’s algorithm; see [ Cormen 2001] for a general discussion of graph algorithms. Dijkstra’s algorithm computes the least- cost path from one node ( the source, which we will refer to as u) to all other nodes in the network. Dijkstra’s algorithm is iterative and has the prop-erty that after the kth iteration of the algorithm, the least- cost paths are known to k destination nodes, and among the least- cost paths to all destination nodes, these k paths will have the k smallest costs. Let us define the following notation:
• D( v): cost of the least- cost path from the source node to destination v as of this iteration of the algorithm.
• p( v): previous node ( neighbor of v) along the current least- cost path from the source to v.
• N : subset of nodes; v is in N if the least- cost path from the source to v is definitively known.
The global routing algorithm consists of an initialization step followed by a loop. The number of times the loop is executed is equal to the number of nodes in the network. Upon termination, the algorithm will have calculated the shortest paths from the source node u to every other node in the network.
Link- State ( LS) Algorithm for Source Node u
1 Initialization:
2 N’ = { u}
3 for all nodes v
4 if v is a neighbor of u
5 then D( v) = c( u, v)
6 else D( v) = 8
7 —-
8 Loop
9 find w not in N’ such that D( w) is a minimum
10 add w to N’
11 update D( v) for each neighbor v of w and not in N’:
12 D( v) = min( D( v), D( w) + c( w, v) )
13 /* new cost to v is either old cost to v or known
14 least path cost to w plus cost from w to v */
15 until N’= N
As an example, let’s consider the network in Figure 4.27 and compute the least- cost paths from u to all possible destinations. A tabular summary of the algorithm’s computation is shown in Table 4.3, where each line in the table gives the values of the algorithm’s variables at the end of the iteration. Let’s consider the few first steps in detail.
• In the initialization step, the currently known least- cost paths from u to its directly attached neighbors, v, x, and w, are initialized to 2, 1, and 5, respectively. Note in particular that the cost to w is set to 5 ( even though we will soon see that a lesser- cost path does indeed exist) since this is the cost of the direct ( one hop) link from u to w. The costs to y and z are set to infinity because they are not directly connected to u.
• In the first iteration, we look among those nodes not yet added to the set N and find that node with the least cost as of the end of the previous iteration. That node is x, with a cost of 1, and thus x is added to the set N . Line 12 of the LS algo-rithm is then performed to update D( v) for all nodes v, yielding the results shown in the second line ( Step 1) in Table 4.3. The cost of the path to v is unchanged. The cost of the path to w ( which was 5 at the end of the initialization) through node x is found to have a cost of 4. Hence this lower- cost path is selected and w’s predecessor along the shortest path from u is set to x. Similarly, the cost to y ( through x) is computed to be 2, and the table is updated accordingly.
• In the second iteration, nodes v and y are found to have the least- cost paths ( 2), and we break the tie arbitrarily and add y to the set N so that N now contains u, x, and y. The cost to the remaining nodes not yet in N , that is, nodes v, w, and z, are updated via line 12 of the LS algorithm, yielding the results shown in the third row in the Table 4.3.
• And so on. . . .
Step N D(v), p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z)
0 u 2,v 5,u 1,u ∞ ∞
1 ux 2,v 4,x 2,x ∞
2 uxy 2,v 3,y 4,y
3 uxyv 3,y 4,y
4 uxyvw 4,y
5 uxyvwz
Table 4.3 Running the link- state algorithm on the network in Figure 4.27
When the LS algorithm terminates, we have, for each node, its predecessor along the least- cost path from the source node. For each predecessor, we also have its predecessor, and so in this manner we can construct the entire path from the source to all destinations. The forwarding table in a node, say node u, can then be constructed from this information by storing, for each destination, the next- hop node on the least- cost path from u to the destination. Figure 4.28 shows the resulting least- cost paths and forwarding table in u for the network in Figure 4.27.
What is the computational complexity of this algorithm? That is, given n nodes ( not counting the source), how much computation must be done in the worst case to find the least- cost paths from the source to all destinations? In the first iteration, we need to search through all n nodes to determine the node, w, not in N that has the minimum cost. In the second iteration, we need to check n – 1 nodes to determine the minimum cost; in the third iteration n – 2 nodes, and so on. Overall, the total number of nodes we need to search through over all the iter-ations is n( n + 1)/ 2, and thus we say that the preceding implementation of the LS algorithm has worst- case complexity of order n squared: O( n2). ( A more sophisti-cated implementation of this algorithm, using a data structure known as a heap, can find the minimum in line 9 in logarithmic rather than linear time, thus reduc-ing the complexity.)
Before completing our discussion of the LS algorithm, let us consider a pathol-ogy that can arise. Figure 4.29 shows a simple network topology where link costs are equal to the load carried on the link, for example, reflecting the delay that would be experienced. In this example, link costs are not symmetric; that is, c( u, v) equals c( v, u) only if the load carried on both directions on the link ( u, v) is the same. In this example, node z originates a unit of traffic destined for w, node x also originates a unit of traffic destined for w, and node y injects an amount of traffic equal to e, also destined for w. The initial routing is shown in Figure 4.29( a) with the link costs cor-responding to the amount of traffic carried.
Destination Link
Z
U
Y
X
V
W
V (u, v)
w (u, x)
x (u, x)
y (u, x) z (u, x) Figure 4.28 Least cost path and forwarding table for nodule u
When the LS algorithm is next run, node y determines ( based on the link costs shown in Figure 4.29( a)) that the clockwise path to w has a cost of 1, while the counterclockwise path to w ( which it had been using) has a cost of 1 + e. Hence y’s least- cost least-cost path to w is now clockwise. Similarly, x determines that its new least- cost path to w is also clockwise, resulting in costs shown in Figure 4.29( b). When the LS algorithm is run next, nodes x, y, and z all detect a zero- cost path to w in the counterclockwise direction, and all route their traffic to the counterclockwise routes. The next time the LS algorithm is run, x, y, and z all then route their traffic to the clockwise routes.
What can be done to prevent such oscillations ( which can occur in any algo-rithm, not just an LS algorithm, that uses a congestion or delay- based link met-ric)? One solution would be to mandate that link costs not depend on the amount of traffic carried— an unacceptable solution since one goal of routing is to avoid highly congested ( for example, high- delay) links. Another solution is to ensure that not all routers run the LS algorithm at the same time. This seems a more reasonable solution, since we would hope that even if routers ran the LS algorithm with the same periodicity, the execution instance of the algorithm would not be the same at each node. Interestingly, researchers have found that routers in the Internet can self- synchronize among themselves [ Floyd Synchronization 1994]. That is, even though they initially execute the algorithm with the same period but at different instants of time, the algorithm execution instance can eventually become, and remain, synchronized at the routers. One way to avoid such self-synchronization is for each router to randomize the time it sends out a link advertisement.
Having studied the LS algorithm, let’s consider the other major routing algo-rithm that is used in practice today— the distance- vector routing algorithm.
