EC310 Lesson 28: Routing Part II objectives

Up until this point we have talked about simple examples where one router is the only path to one network. In reality, things are much different. Often there can be multiple paths from one network to another. The question is not just how to get from Point A to Point B, but how to get there using a good route.

• 
  Correctness—packets should be routed to the proper destination.
  

• 
  Simplicity—algorithms should clean and simple so that packets are routed quickly to their destinations. Unwieldy Rube Goldberg-type algorithms are to be avoided.
  

• 
  Robustness—algorithms should adapt to changes in the network's topology caused by router or link failures.
  

• 
  Stability—the algorithm should converge to a specific solution; packets should not be left aimlessly circulating in loops around the network.
  

• 
  Optimality—if there are multiple ways to get from Point A to Point B, the algorithm should provide the optimal path through the network.
  

Routing is accomplished by routing protocols which establish routing tables in each router. The router consults its table to determine how to route packets.

distance shortest path

cost cheapest path

queuing delay fastest path

• 
  all explicit directions correctly point to a shortest path
  
• 
  all shortest paths for all destinations be explicitly noted in the tables
  

Note that routers make local routing decisions – i.e., they decide the next place to send a packet addressed to a specific destination. But they must make this decision based on some understanding of the global network picture. So, each router needs global information about the network. It is somewhat confusing, so the point bears repeating: Routers make local routing decisions based on global information.

Recall that routing protocols establish routing tables in each router, and, as a simplification, we can say that these tables have the following format:


Destination address Address of the next element on the best path to the destination

When a packet shows up at a router, the router refers to the routing table to decide where to send the packet.

Routing Table for Router 1:
destination next element

2 2

3 3

4 2

5 3

6 3 7 3 8 3

9 3

10 2

Example 1
Consider the network shown below, where the numbers on the edges indicate the cost of using that edge. For example, the cost of using the link from Router A to Router B is 1, whereas the cost of using the link from Router A to Router D is 4.
(a) Draw the routing table for Router A.


Solution:
Destination Next Hop

B

C

D

E

F

(b) If all routers have the correct routing tables, what is the path that an IP packet travels from Node A to Node F? (Note that to state a path, you just need to state the sequence of routers encountered along the path; for example, one possible path from Router A to Router F is A-D-E-F.
Solution:
(c) What is the total cost of the path you selected in Part (b) above?
Solution:

II. Routing Protocols
So, now that we know what routing tables should look like, we ask the question: How do routing tables actually get put together? You likely solved the preceding example by looking down on the network and performing a visual analysis of the picture. Routers do not have the ability to hover over a picture of the network, and they do not have human visual skills at their disposal for use in analyzing a diagram.

Routers use routing protocols to build their routing tables. Routing protocols are intended to:

• 
  Communicate network topology information to each router.
  

• 
  Determine how individual routers will use this information to make routing decisions (i.e., determine how individual routers will use this information to construct routing tables like the one shown above).
  

We will discuss two routing methodologies: Link State Routing and Distance Vector Routing.

1. Link State Routing
A. Two key ideas:

• 
  Each router learns the full network topology. That is, each router learns a complete picture of the network graph–the routers, the links and the link weights.
  

• 
  Knowing the complete network picture, each router independently computes the optimal routes to each destination and constructs a routing table.
  

B. Learning the topology.

The first bullet above says “routers learn the full network topology.” So, in link state routing, how do routers come to know the network topology? Here's how!

• 
  Each router learns its neighbors’ addresses by sending "Hello" packets to which its neighbors reply.
  

• 
  Each router determines the weight of each of its links. For example, if these weights represent time delays, the routers might determine how long it takes to receive a reply, and use that as the weight. If the weight is a cost, the router might “know” the costs associated with each link based on data entered by a network administrator.
  

• 
  Each router then transmits packets that tell information about that individual router's links.
  

For instance, in the picture below, Router 26 sends a packet that essentially says:

My name is Router 26
Router 18 is connected to me and the weight of the edge joining us is 4
Router 35 is connected to me and the weight of the edge joining us is 2
Router 51 is connected to me and the weight of the edge joining us is 3

Or, somewhat more formally, it transmits a packet that conveys the following table.

26 _____

18 4

35 2

51 3
By sending this packet, a router informs the network about the status, or state, of each of its links. Hence, this methodology is called Link State Routing and these packets are called Link State Packets (LSPs). This info will then be used by others to construct routing tables.

These LSPs are distributed to all other routers using "controlled flooding": When a router receives a LSP, it gives it to all of its neighbors. A router keeps track of which LSPs it has seen, and only floods them the first time they arrive.
Now…think about this: After each router has sent its LSP, and after each LSP has circulated to all the other routers, then does each router have a full and complete picture of the network topology? The answer is Yes!
But what then—we still don't have routing tables in each router? Answer: Each router runs Dijkstra’s Algorithm. This is a well-known algorithm which solves this problem (the details of which we skip).
It is important that the fundamental idea be understood: In link state routing:

• 
  Each router, in its LSP, sends information about its neighbors only.
  

• 
  The information in this LSP is sent to all other routers.
  

An Aside

Do routers really have names like 'Router 26'? Yes! In the Internet's OSPF routing protocol, a router identifies itself to all other routers using a unique IP address called a Router ID.  Additionally, in every OSPF message a router sends it will include its Router ID  so that other routers know who originated the message and where they can be reached.  For this reason it is very important that the IP address assigned as the Router ID is always available.  
As you know, hardware (like your trusty drill rifle) is prone to failure.  Therefore, a special software interface called the loopback interface is assigned the Router ID.  The loopback interface, because it is enabled in software, is always active regardless if one or two hardware interfaces on a router stop working.  This ensures routers can always find each other to communicate when needed.
What are the routers talking about with each other and why do they need to communicate so often? There are a number of internal measures routers use in order increase efficiency and prevent unnecessary information from clogging up the network, such as electing a Designated Router (DR) and Backup Designated Router (BDR) and managing Link State Updates (LSU). 
To learn more about OSPF, see http://www.ietf.org/rfc/rfc2328.txt.

An Aside

Because of time constraints in EC312, we just say:
Each router runs Dijkstra’s Algorithm. This is a well-known algorithm which solves this problem (the details of which we skip).
You should know, though, that the algorithm is truly one of the all-time-beauts in network theory.
The algorithm solves the problem: Find the shortest path from Node X to every other node in an arbitrary network where the edges have nonnegative weights associated with them. The algorithm is not hard, but would require a full period (perhaps) to fully explain it. Many reasonably good explanations can be found on the web. An explanation (not so good) can be found in your text in Chapter 20.
Dijkstra's Algorithm has two interesting (non-technical) facts associated with it.
First, the algorithm was published in 1959. We realize that to the average midshipmen, the year 1959 might as well be 1659, but—truth be told—1959 is really not that long ago! It is fascinating to think that the basic problem of determining the shortest path in a network eluded the great minds throughout history—Euclid, Euler, Newton, Leibniz, Descartes, Fermat, Hilbert—not to be discovered until 1959.
Second, the algorithm was published in a journal article that was strikingly brief. The paper presenting this earth-shattering result was slightly over two pages long. Just two pages! Next time your History prof tells you that your paper needs to be 10 pages to say anything of value, reply: "WRONG! Haven't you heard of Dijkstra!"
Dijkstra had a number of interesting personal idiosyncrasies. Despite the fact that he invented the field of structured computer programming and contributed a key concept (the semaphore) to the study of operating systems, he limited his own use of computers. Until the time he retired from academe in 2000 he wrote all his

papers by hand, used only the chalkboard for teaching, and strictly limited his computer use to web

browsing and email. He passed away in 2002 at age 72.
Example 2
Given the following network map with the weights of edges between routers:

(a) Construct the Link State Packet (LSP) that Router C would send to Router B.
Solution:

Router
Weight

Download 416.85 Kb.

Share with your friends: