Unicast Routing Protocols

Unicast vs. Multicast

In unicast routing a packet needs to go from a single source to a single destination, while in multicast routing the packet needs to go from a single source to several destinations.

Routing Table

A routing table is a database that contains information about the topology of a network. A router consults a routing table when a datagram is ready for sending. A routing table can be static or dynamic. A static routing table contains information entered manually. The administrator enters the route for each destination into the table. A dynamic routing table is updated periodically by using one of the dynamic routing protocols such as RIP, OSPF, or BGP. Whenever there is a change in the Internet, such as a shutdown of a router or breaking of a link, the dynamic routing protocols update all the tables in the routers (and eventually in the host) automatically.

The following are common fields in a routing table:

• Mask. This field defines the mask applied for the entry.
• Network address. This field defines the network address to which the packet is finally delivered. In the case of host-specific routing, this field defines the address of the destination host.
• Next-hop address. This field defines the address of the next-hop router to which the packet is delivered.
• Interface. This field shows the name of the interface.
• Flags. This field defines up to five flags. Flags are on/off switches that signify either presence or absence. The five flags are U (up), G (gateway), H (host-specific),
• Reference count. This field gives the number of users of this route at the moment. For example, if five people at the same time are connecting to the same host from this router, the value of this column is 5.
• Use. This field shows the number of packets transmitted through this router for the corresponding destination.
• · Metric. This field assigns the cost for passing through network. A single network may have different metrics because different protocols assign metrics differently.

Autonomous System

An internet can be so large that using a single protocol to update all routers in the internet would be very inefficient. Thus the internet is divided into groups of networks and routers called autonomous systems. A single autonomous system is managed by a single administration.

Interior and Exterior Routing

Routing inside an autonomous system is called interior routing. In interior routing, the IP datagram travels from a router to another router of the same network. Routing between autonomous systems is called exterior routing. In exterior routing, an IP datagram travels from a router of one network to the router of another network. Each autonomous system can choose the routing protocol it implements for interior routing. Popular protocols for interior routing are Routing Information Protocol (RIP) and Open Shortest Path First (OSPF). An internet uses only one exterior routing protocol. A popular exterior routing protocol is Border Gateway Protocol (BGP).

The RIP treats all networks as equals. The cost of passing through all routers is one hop count. The OSPF allows the administrator to assign a cost depending on the service required (such as throughput or minimum delay). The BGP assigns metrics based on criterion.

Routing Information Protocol Updating Algorithm

Receive: a response RIP message

1. Add one hop to the hop count for each advertised destination.

2. Repeat the following steps for each advertised destination:

1. If (destination not in the routing table)

1. Add the advertised information to the table.

2. Else If (next-hop field is the same)

1. Replace entry in the table with the advertised one.

2. Else If (advertised hop count smaller than one in the table)

1. Replace entry in the routing table.

3. Return.

Open Shortest Path First (OSPF)

Autonomous System Boundary Routers are responsible for delivering information about other autonomous systems into the current system. Within the autonomous system, the OSPF divides the hosts into areas. Each area has a area border router which summarizes information in the area and distributes it to other areas. All areas are connected to a special area called a backbone and areas can be connected to other areas. The backbone has the AS boundary router. If the direct connection between an area and the backbone the administrator must create a virtual link which may pass though several other areas.

OSPF Connections

• The point-to-point link connects two routers without any other host or router in between.
• The transient link is a network with several routers. Data can come in and out of the network through all the routers. All LANs and some WANs are of this type. To avoid a mesh topology, a router called a designated router is positioned at the center such that every other router has only one neighbor which is the designated router. The designated router is not an additional router. One of the existing routers is “designated” with the task.
• The stub link is a special case of the transient link where the number of routers equals one. All data going in and out of the network pass through this router.
• The virtual link is created when the direct link between two routers has been broken. Because it is not anymore possible for the data to go from router A to router B directly then the data would need to pass fro from router A to router C to router E then finally to router B for example.

Link State Advertisement

Link state advertisements serve to inform the network about the information of an entity’s neighbors. The type of LSA depends on the different entities that broadcast them.

1. Router LSA - the router announces its presence and lists the links to other routers or networks in the same area, together with the metrics to them. Type 1 LSAs are flooded across their own area only.

2. Network LSA - the designated router on a broadcast segment (e.g. Ethernet) lists which routers are joined together by the segment. Type 2 LSAs are flooded across their own area only.

3. Summary LSA to Network - an Area Border Router (ABR) takes information it has learned on one of its attached areas and it can summarize it (but not by default) before sending it out on other areas it is connected to. This summarization helps provide scalability by removing detailed topology information for other areas, because their routing information is summarized into just an address prefix and metric.

4. ASBR-Summary LSA - this is needed because Type 5 External LSAs are flooded to all areas and the detailed next-hop information may not be available in those other areas. This is solved by an Area Border Router flooding the information for the router (i.e. the Autonomous System Boundary Router) where the type 5 originated.

5. External LSA - these LSAs contain information imported into OSPF from other routing processes. They are flooded to all areas (except stub areas).

Topology distribution

When applying link-state algorithms, each node uses as its fundamental data a map of the network in the form of a graph. To produce this, each node floods the entire network with information about what other nodes it can connect to, and each node then independently assembles this information into a map. Using this map, each router then independently determines the least-cost path from itself to every other node using a standard shortest paths algorithm such as Dijkstra's algorithm.

Distance vector algorithms use the Bellman-Ford algorithm. The algorithm operates in a very simple manner. When a node first starts, it only knows of its immediate neighbors, and the direct cost involved in reaching them. (This information, the list of destinations, the total cost to each, and the next hop to send data to get there, makes up the routing table, or distance table.) Each node, on a regular basis, sends to each neighbor its own current idea of the total cost to get to all the destinations it knows of. The neighboring node(s) examine this information, and compare it to what they already 'know'; anything which represents an improvement on what they already have, they insert in their own routing table(s). Over time, all the nodes in the network will discover the best next hop for all destinations, and the best total cost.

Path vector routing is used for exterior routing. Path vector routing became the basis of the Border Gateway Protocol (BGP). It is similar to distance vector routing. In path vector routing we assume there is one node (there can be many) in each autonomous system which acts on behalf of the entire autonomous system. This node is called the speaker node (or autonomous system boundary router). The speaker node creates a routing table (containing the destination, next hop and the path) and advertises it to neighboring speaker nodes in neighboring autonomous systems. The idea is the same as distance vector routing except that only speaker nodes in each autonomous system can communicate with each other.

The Dijkstra algorithm

The Dijkstra (silent j) algorithm is an algorithm which determines the best (shortest) route from a single node to all other nodes. Each route is one source to one destination. The source of the route is only one node but the destination changes though there is only one destination for every shortest route. Thus this is very useful for unicast routing wherein the source node (which is permanent) should know the shortest path to a single destination node (which changes).

Dijkstra algorithm is as follows

1. Start with the local node (router): the root of the tree.

2. Assign a cost of 0 to this node and make it the first permanent node.

3. Examine each neighbor node of the node that was the last permanent node.

4. Assign a cumulative cost to each node and make it tentative.

5. Among the list of tentative nodes

1. Find the node with the smallest cumulative cost and make it permanent.

2. If a node can be reached from more than one direction

1. Select the direction with the shortest cumulative cost.

6. Repeat steps 3 to 5 until every node becomes permanent.

Internet Group Management Protocol

IGMP is a group management protocol. It helps a multicast router create and update a list of loyal members related to each router interface through messages. The types of messages are membership report, leave report and query.

Membership Report - Joining a Group

A host or a router can join a group. A host maintains a list of processes that have member-ship in a group. When a process wants to join a new group, it sends its request to the host. The host adds the name of the process and the name of the requested group to its list. If this is the first entry for this particular group, the host sends a membership report message. If this is not the first entry, there is no need to send the membership report since the host is already a member of the group; it already receives multicast packets for this group.

Leave Report - Leaving a Group

When a host sees that no process is interested in a specific group, it sends a leave report. Similarly, when a router sees that none of the networks connected to its interfaces is interested in a specific group, it sends a leave report about that group.

Query – Monitoring Membership

The router periodically (by default, every 125 s) sends a general query message. In this message, the group address field is set to 0.0.0.0. This means the query for membership continuation is for all groups in which a host is involved, not just one.

Bibliography

Forouzan, B. (2003). Data Communications and Networking 3rd ed. New York: McGraw Hill.

Forouzan, B. (2007). Data Communication and Networking 4th ed. New York: McGraw Hill.

Link-state advertisement. (n.d.). Retrieved October 10, 2010, from Wikipedia: http://en.wikipedia.org/wiki/Link-state_advertisement

Routing. (n.d.). Retrieved October 10, 2010, from Wikipedia: http://en.wikipedia.org/wiki/Routing