2.7 Routing


Routing of datagrams across the Internet is acomplished by routing protocols. Routers and switches are responsible for making decisions about what path on which to send a packet for it to reach its destination. So how do routers and switches acquire the information that allows them to route and forward packets correctly? Routing is a complex problem, and the fundamentals of this technology are based in graph theory. The basic problem of routing is to find the lowest -cost path between any two nodes. The cost of a path is determined by distance or other factors.

Routing in small networks with only a few hosts can be accomplished easily by configuration of the route tables. This is referred to as static routing. However, when we start scaling, the need for dynamic routing protocols becomes obvious quickly. Routing protocols provide a distributed and dynamic way to solve the problem of finding the lowest-cost path in the presence of link and node failures and changing edge costs. Static routing is useful in some special cases, such as to define a default route that is not being advertised in the network or to supplement an exterior gateway protocol. Dynamic routing protocols can be classified into two groups:

  • Interior Gateway Protocols (IGPs) Examples of these are rowing information protocol (RIP) and open shortest path first (OSPF).

  • Exterior Gateway Protocols (EGPs) An example of this is border gateway protocol (BGP).

Gateway protocols are referred to as interior or exterior depending on whether they are used within or between autonomous systems (ASs). An autonomous system can be viewed as a logical portion of a much larger IP network. The concept of autonomous systems allows the scalability of routing protocols. IGPs exchange routing information within the confines of the AS. EGPs allow the exchange of reachability information between ASs.

Two main classes of routing protocols exist: distance vector and link state .

2.7.1 Distance Vector Routing

Distance vector routing is based on the concept of each node maintaining the distance from itself to every other node that it is aware of. Distance vector tables consist of a series of destinations and the costs associated with each to reach them. The distance to other nodes is learned via information provided by neighboring routers. Each router transmits its own distance vector table across the shared network. The following steps are generally involved in the setup of a distance vector table:

  1. Each router initializes itself with a distance vector table that contains 0 as the distance for itself, 1 as the distance to directly attached networks, and infinity for all other networks.

  2. Each router in the network periodically distributes its distance vector table to each of its neighbors.

  3. Each router saves the most recent table that it receives and uses this information to compute a distance vector table.

  4. Total cost to each destination is computed by adding the cost reported to it by each neighbor's distance vector table.

  5. . Each router then generates its own routing/forwarding table based on the lowest cost for each destination.

The preceding algorithm produces a stable routing table after a period that is directly related to the number of routers in the network. This stabilization time is refered to as convergence. The route tables are recomputed if a change is received from one of the neighbors or if a link state changes.

2.7.2 Link State Routing

Large networks have demonstrated the inefficiencies of distance vector routing. This has resulted in a different approach to tackling routing. The new protocols that have been designed are based on what is refered to as link state or shortest path first (SPF) algorithms. The principle of link state routing is relatively straightforward and based on Djikstra's algorithm. A very high-level view of the principles and algorithm is as follows :

  • Routers are responsible for contacting their neighbors and learning their identities.

  • Routers construct link state packets that contain information about the list of networks and their states. These are transmitted to all routers in a network.

  • All routers have identical information about available links and the link states in a network, which results in a common topology view in all routers.

  • These topology maps are utilized to construct the best routes to each destination.

Routers contact neighbors by sending Hello packets on their network interfaces. Hello packets are sent directly to neighbors on point-to-point networks and nonbroadcast networks. On multiaccess networks these packets are sent to a predefined group or a multicast IP address. Neighbors that receive these hello packets respond with their identities. Once neighbors have been contacted, link state information is exchanged via link state packets (LSPs). LSPs are distributed to all routers in a network via flooding mechanisms. All routers must acknowledge the reception of an LSP. Flooding ensures that all routers in a network have the same link state information. Each router in the network uses the information in the LSPs in the SPF algorithm to generate a shortest path tree with itself as the root. LSPs are sent every time a new router is added or deleted, when a link to a neighbor goes down, or when the cost associated with the link changes. In addition, refresh packets are sent on a periodic basis (~30 min.) to maintain sanity of the routing state.

2.7.3 Interior Gateway Protocols

RIP, RIPv2, OSPF, and Inter System-Inter System (IS-IS) are the standard IGPs. RIP is defined in RFC 1058 and is suitable for small networks. Problems that were identified with RIP were addressed in a subsequent release called RIPv2. RIP runs on top of UDP and uses port 520. RIPng is the version of RIP that is defined for IPv6 networks and is documented in RFC2080. RIPng uses port 521 for sending and receiving packets. OSPF is a link state protocol that is widely used in networks today and is the predominant routing protocol in medium to large networks. OSPF incorporates many features that make it the default choice in many cases. OSPFv2 is defined in RFC 2328.

2.7.4 Exterior Gateway Protocols

EGPs are used to exchange routing information between routers in different autonomous systems. EGPs include EGP, which is defined in RFC 904 and is now considered historical; and Border Gateway Protocol, BGP-4, which is described in RFC 1771. BGP is based on the Classless Internet Domain Routing (CIDR) concept. BGP runs over a reliable transport protocol (TCP) between neighbor routes. TCP port 179 is used by BGP speakers . The BGP protocol comprises four main stages:

  • Opening and confirming a BGP connection over TCP with a neighboring router.

  • Maintaining the BGP connection via keepalive messages.

  • Sending reachability information via update messages to its neighbors.

  • Notification of error conditions when they occur. This results in the closing of the TCP connection.

Routing protocols continue to evolve as the Internet grows large. The size of the Internet and rapid growth have put a lot of pressure on routing protocols. As route tables increase in size, efficiency of routing tends to go down. These issues and others related to routing are dealt with in the industry on a constant basis and keep the Internet humming.

2.7.5 Routing for Mobile Hosts

As the number of wireless networks that support IP grows, as well as the number of notebook computers, PDAs, and mobile phones with IP capability, the need for supporting mobility in IP networks becomes greater. The Internet protocol, when designed in the early 1970s and 1980s, did not take into consideration the need for supporting mobility. The need to support seamless mobility was felt more in the 1990s. Note that there is a difference between seamless mobility and nomadic mobility.

Seamless mobility: Mobility in which the sessions and the applications on the device are uninterrupted as the terminal changes its point of attachment to the network. An example of seamless mobility is a user making a voice call (via a wireless network) while driving in a car and the call is uniterrupted while it is handed off between base stations .

Nomadic mobility: Mobility in which the sessions and applications are restarted as a result of the user moving from network connectivity at point A to network connectivity at point B. An example of nomadic mobility is a user connected to the corporate network and then traveling to another location (e.g., hotel) and connecting to the corporate network via dialup and restarting the applications.

THE PROBLEM

Most applications today use TCP as the transport protocol. When a TCP connection is set up, the entities on either side know the IP address associated with the other end. The IP address of a node is based on its point of attachment to the network, and routing in the Internet is based on the network addresses. So when a node changes its point of attachment, the IP address associated with the interface changes. As a result, the TCP connection serving an application is torn down as the connection endpoints are identified by the combination of port number and IP address. The connection cannot survive a change in IP address.

THE SOLUTION

Mobile IP was designed in the IETF to address IP layer mobility, specifically to address the problem described in the previous subsection. The specification for Mobile IP is in RFC 3344. Mobile IP solves the problem by introducing a couple of new network elements. The Home Agent and the Foreign Agent enable a mobile host to move across different points of attachment, which results in a change to the interface's IP address. However, the existing connections are maintained . This is accomplished by a little help from the home agent and the foreign agent. The mobile node, when it moves from its home network to another network or point of attachment (which is served by a foreign agent) acquires a care-of address. So the mobile node has its home IP address as well as a care-of address associated with its interface. It registers this care-of address with its home agent, which is a router on its home network. The home agent proxies for the mobile node and intercepts all packets destined for the mobile node. This is accomplished via a process known as proxy ARP. The home agent then tunnels the packets destined for the mobile node to the care-of address. The mobile node always uses its home IP address in any sessions with correspondent nodes. Since the home IP address is always constant, TCP sessions survive the change in network attachment points. The only thing that changes as the mobile moves is the care-of address. However, since the endpoint of the TCP connection is unaware of the care-of address, there is no impact to the session. Packets from the mobile node to the correspondent nodes are directly routed to it. However, packets from the correspondent node to the mobile arrive at the home agent and are tunneled to the mobile via the care-of address. This is commonly refered to as triangle routing.

The IP mobility solution for IPv6 is slightly different from the one for IPv4, which was just described. In IPv6 there is no foreign agent. The problem of triangle routing is also eliminated by a mechanism known as route optimization. The mobile node can inform a correspondent about its care-of address and thus have the session ongoing between itself and the correspondent without any need for the home agent. However, the home agent still exists in IPv6, and the functionality of the home agent is the same as in Ipv4. The mobility protocol for IPv6 is in the process of being standardized in the IETF at the time of this writing.



IP in Wireless Networks
IP in Wireless Networks
ISBN: 0130666483
EAN: 2147483647
Year: 2003
Pages: 164

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net