Powered By Blogger

Thursday, October 7, 2010

Unicast and Multicast Routers: Routing Protocols

Unicast routing vs. Multicast routing

In unicast communication, there is one source and one destination. The relationship between the source and the destination is one-to-one. Source and the destination addresses in the IP diagram are the unicast addresses assigned to the host. In unicast routing, the router forwards the received packet through only one of its ports.

In multicast routing there is one source and a group of destinations. The relationship is one-to-many. The source address is a unicast address, but the destination address is a group address. In multicast routing, the router may forward the received packet through several of its ports.

Autonomous System (AS) is a group of networks and routers under the authority of a single administration. Internet today is so large that one routing protocol cannot handle the task of updating the routing tables of all routers. The figure below shows how it may work in the Internet world.

Autonomous Systems can be grouped into three categories, depending on their connectivity and operating policy.

A multihomed Autonomous System is an AS that maintains connections to more than one other AS. This allows the AS to remain connected to the Internet in the event of a complete failure of one of their connections. However, this type of AS would not allow traffic from one AS to pass through on its way to another AS.

A stub Autonomous System refers to an AS that is connected to only one other AS. This may be an apparent waste of an AS number if the network's routing policy is the same as its upstream AS's. However, the stub AS may in fact have peering with other Autonomous Systems that is not reflected in publivsc route-view servers. Specific examples include private interconnections in the financial and transportation sectors.

A transit Autonomous System is an AS that provides connections through itself to other networks. That is, network A can use network B, the transit AS, to connect to network C. ISPs are always transit ASs, because they provide connections from one network to another. The ISP is considered to be 'selling transit service' to the customer network, thus the term transit AS. (Wikipedia)


Interior routing Protocol vs. Exterior routing Protocol

An interior routing protocol such as RIP handles

routing inside an autonomous system. An exterior routing protocol such as BGP handles routing between autonomous systems.

Routing Table- a table containing infor

mation a router needs to route packets. The information may include the network address, the cost, the address of the next hop, and so on.

The routing table consists of at least three information fields:-

1. the network id: i.e. the destination network id

2. cost: i.e. the cost or metric of the path through which the packet is to be sent

3. next hop: The next hop, or gateway, is the address

of the next station to which the packet is to be sent on the way to its final destination

Depending on the application and implementation, it can also contain additional values that refine path selection:

1. quality of service associated with the route.

For example, the U flag indicates that an IP route is up.

2. links to filtering criteria/access lists associated with the route

3. interface: such as eth0 for the first Ethernet card

, eth1 for the second Ethernet card, etc.

Host id

Cost

Next hop

........

........

........

........

........

........


Open Shortest Path First (OSPF) is an adaptive routing protocol for Internet Protocol (IP) networks. It uses a link state routing algorithm and falls into the group of interior routing protocols, operating within a single autonomous system (AS). OSPF defines four types of links (networks): point-to-point, transient, stub, and virtual.

A point-to-point link connects two routers without any other host or router in between. The purpose of the link is just to connect the two routers. An example of a point-to-point link is two routers connected by a telephone line or T-line.

A transient link is a network with several routers attached to it. The data can enter through any of the routers and leave through any router. All LANs and some WANs with two or more routers are of this type.

A stub link is a network that is connected to only one router. The data packets enter the network through this single router and leave the network through this same router.

Virtual link on the other hand is used in network where routers are broken; the administrator may create a virtual link which is a longer path that probably goes through several routers. The link is only unidirectional from the router to the network.


Link State Advertisement


A link state advertisement announces the states of entity links. Depending on the type of entity, there can be five different LSAs can be define: router link, network link, summary link to a network, summary link to AS boundary router, and external link.


Path Vector Routing

Path vector routing is used for inter-domain

routing. 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. The speaker node creates a routing table and advertises it to neighboring speak

er 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 speaker node advertises the path, not the metric of the nodes, in its autonomous system or other autonomous systems. Path vector routing is discussed in RFC 1322; the path vector routing algorithm is somewhat similar to the distance vector algorithm in the sense that each border router advertises the destinations

it can reach to its neighboring router. However, instead of advertising networks in terms of a destination and the distance to that destination, networks are advertised as destination addresses and path descriptions to reach those destinations. A route is defined as a pairing between a destination and the attributes of the path to that destination, thus the name, path vector routing, where the routers receive a vector that contains paths to a set of destinations. The path, expressed in terms of the domains (o

r confederations) traversed so far, is carried in a special path attribute that records the sequence of routing domains through which the reachability information has passed. (Wikipedia)


Dijkstra Algorithm

It calculates the shortest path between two points on a network, using a graph made of nodes and edges.

OSPF, a unicast routing protocol, uses link

state routing, which is

based on the Dijkstra algorithm.

The algorithm divides the nodes into two sets: tentative and permanent. It chooses nodes, makes them tentative, examines them, and if they pass the criteria makes them permanent. We can informally define the algorithm using the following steps:

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.


IGMP (Internet Group Management Protocol) is a group management protocol. It is not a multicasting routing protocol; it is a protocol that manages group membership. It has three types of messages: query message, the membership report, and the leave report.


1. 1. Membership report is used when a host or a router joins a group. When a process wants to join a new group, it sends its request to the host.

2. 2. Leave report message is sent when a host sees that no process is interested in a specific group. Same for the routers, when it sees that none of the networks connected to its interfaces is interested in a specific group.

3. 3. Query message has two types, general and special. The above two reports will not be enough to monitor membership. The multicast router is responsible for monitoring all the hosts or routers in a LAN to see if they want to continue their membership in a group.




No comments:

Post a Comment