|
Site home page Get alerts when Linktionary is updated Book updates and addendums
Get info about the Encyclopedia of Networking and Telecommunicatons, 3rd edition (2001)
Download the electronic version of the Encyclopedia of Networking, 2nd edition (1996). It's free! Contribute to this site Electronic licensing info
|
Routing Related Entries Web Links New/Updated Information Note: Many topics at this site are reduced versions of the text in "The Encyclopedia of Networking and Telecommunications." Search results will not be as extensive as a search of the book's CD-ROM. This topic discusses routing protocols and algorithms. See "Routers" for a discussion of hardware routing devices and "Multilayer Switching" for a discussion of layer 3 switches (routing switches). A historical perspective on the development of routing on the Internet is referenced under "Routing on the Internet." Also note that this topic covers IP routing, although other routable protocols such as IPX (Internetwork Packet Exchange) exist. Routing is a packet-forwarding process that takes place on internetworks (i.e., separate networks that are joined by routers), as shown in the following illustration. When a host sends a packet, it is either for a local host on the same network or a host on a remote network. If the packet does not have a local IP network address, the host sends the packet to the default router, which forwards the packet to other networks. Illustration (see book) The network in the following illustration is more complex. It consists of a mesh of interconnected networks that provide multiple routing paths. While each router may have its own attached networks and hosts, only two hosts are shown for simplicity. Host A wants to send a packet to host B. Multiple paths exist. Host A sends the packet to its locally attached router and lets the router handle the forwarding. Illustration (see book) How does the router choose a path? It looks in a routing table that has been created with the help of a routing protocol. By looking in its routing table, router A will find two paths. One is preferred, while the other is available should the preferred path go down. An administrator may designate a preferred path by setting metrics. Routers are responsible for determining the next hop that will get a packet to its destination, not the complete path to the destination. Basic IP routing is called hop-by-hop or destination-based routing. The technique is like getting directions-a person may point you in the right direction at an intersection. At the next intersection, another person points you in the right direction. Eventually, you get to where you want to go-not by knowing the exact path from the start, but by being pointed along the way as you go. Someone might point you in a direction that avoids construction or dead ends. On a large meshed network with many possible paths, routers may choose paths that avoid congested or temporarily disabled links. Router-based internetworking is essential for building scalable networks. It promotes a hierarchical network structure and network addressing scheme. Data link layer LANs are limited by size and number of hosts. Routing helps networks grow beyond these limitations. Network designers can use routing to join multiple LANs into internetworks. On the Internet, routers allow independently managed autonomous systems (ASs) to interconnect and exchange traffic while maintaining the autonomy of each network. Routing Procedures The original requirement for routers (originally called "gateways") on the early Internet was for a device that could inspect an incoming packet and read its destination address, look this address up in a table, and then forward the packet appropriately. A router may need to fragment packets to fit the frame size of the underlying network. Routers may drop packets in an overflow situation. TCP is responsible for detecting and recovering dropped packets. One of the most comprehensive documents on routing is RFC 1812 (Requirements for IP Version 4 Routers, June 1995). Originally, the lookup tables were manually configured by network administrators, a process known as static routing. Static routing is appropriate for small networks and some dedicated links, but with large networks, dynamic routing is a requirement. Network topologies may change at any time when links fail or link metrics are reconfigured. A dynamic routing protocol must discover these changes and update routing tables. Several routing protocols and algorithms have been devised to handle this task, as discussed later. The internetwork routing process is pictured in Figure R-5 and outlined here. For simplicity, the numeric IP addresses of networks, hosts, and routers are replaced with abbreviations.
Host C1 sees the frame on the network as being addressed to it, and receives the frame. To transmit large files, the file is broken into pieces that are put inside numerous packets. Then, if one of the packets is lost, only that packet must be retransmitted and not the entire file. This reliability feature is handled by TCP in the background. Routing Environments A basic routing concept is the autonomous system, as shown in Figure R-6. The Internet is a collection of autonomous systems in the form of individual service providers and carrier networks that are interconnected by routers, routing protocols, and routing policies. Each autonomous system is managed by its own authority and implements its own internal routing. An autonomous system is essentially a routing domain. The same interior routing protocols and algorithms are used within a domain. OSPF is the most popular interior routing protocol. Routing among autonomous systems is called exterior routing. BGP is the exterior routing protocol for the Internet. Interior routing is sometimes called "intradomain routing" and exterior routing is sometimes called "interdomain routing." External connections are made via a border router, which provides a gateway to the outside world. A border router provides "reachability" information for all of its internal routes to border routers belonging to other ASs. This information is quite succinct and often consists of a single routing table entry (for external routers) that represents all of the internal networks on the other side of the border router. A range of contiguous network addresses may be represented by a single (larger) network address. This scheme greatly reduces the amount of routing information that must be stored and transmitted on the Internet. The Internet is made up of many autonomous systems consisting of local, regional, and backbone service providers. See "Internet Architecture and Backbone" for information about the architecture of the Internet. Routing Protocols and Algorithms Dynamic routing protocols automatically discover routes on the network and build routing tables. Routers refer to the tables when forwarding packets. As mentioned, there are interior and exterior routing protocols. The primary interior routing protocols in use today are RIP (Routing Information Protocol) and OSPF (Open Shortest Path First). OSPF is now the most important on large networks and Internet service provider networks, but RIP is still popular for small private networks. The primary exterior routing protocol for exchanging routing information between autonomous systems is BGP (Border Gateway Protocol). A dynamic routing protocol adjusts to changing network topologies, which are indicated in update messages that are exchanged between routers. If a link attached to a router goes down or becomes congested, the routing protocol running in the router makes sure that other routers know about the change. It then runs a routing algorithm to recalculate the routes on the network and update the routing tables. Routers store the information about the network in routing tables. These tables contain an entry for each known network along with a reference to the interface that leads to that network. The next router in the path will make a similar routing decision based on information it finds in the routing table that it has created. Note that each router has different routing table entries because the reachability of each network is different depending on its location in the mesh. "Route flapping" is the frequent changing of the availability of routes. When a route changes, some routers are likely not to get the new route information and continue forwarding packets into the old erroneous route (usually called a "black hole"). Over the years, a number of routing protocols have been developed. These include distance-vector routing protocols and link-state routing protocols, with the latter being the most preferred on today's large internetworks. See the following topics for more information:
You can also refer to "VRRP (Virtual Router Redundancy Protocol)." This protocol provides uninterrupted rerouting in the event of a router failure. It relies on statically configured redundant routers. Alternative routing techniques are handled in IP over ATM environments, where ATM networks provide the data link layer for IP networks. In this environment, methods are needed to discover routes across the ATM network among routers at the edge of the ATM network. Cut-through routing (sometimes called "shortcut routing") is an approach in which a cut-through route is created between end systems as a virtual circuit across an ATM switching fabric. The first few packets are initially routed, but if a long flow is detected, the ATM address of the destination is obtained by the source, which then sets up a virtual connection across the ATM fabric directly to the destination, switching all subsequent packets and bypassing the routers. See "IP over ATM" for more information. MPLS (Multiprotocol Label Switching) is the latest solution for delivering QoS and traffic engineering across IP networks. It provides explicit routing and constraint-based routing. Beth set up paths that have the characteristics of a virtual circuit in a switched environment. With explicit routing, a path is created across a network between two points in advance of sending packets. Packets are tagged with the label of the path and switched across the network. Constraint-based routing takes this concept further by defining how intelligent routing software can gather information about network loads, bandwidth characteristics, and jitter/delay characteristics. Paths are then selected based on various constraints. An administrator may simply want to balance the load across the network, ensuring that one link is not underused while another is overused. A path may also be selected because it provides enough bandwidth to carry a particular stream. This goes beyond the concept of using metrics to engineer routes. Instead, advanced routing software dynamically selects routes based on the current network environment. See "Traffic Management, Shaping, and Engineering." Additional Information The IETF has a number of working groups that are working on routing and routing-related issues. The following IETF Web site has a list of routing-related working groups listed under the topic "Routing Area."
The following RFCs provide information about routing and routing protocols.
Copyright (c) 2001 Tom Sheldon and Big Sur Multimedia.
|
