Interior Gateway Protocols (IGP) are used for intra-autonomous system routing - routing inside an autonomous system. Exterior Gateway Protocols (EGP) are used for inter-autonomous system routing - routing between autonomous systems

Characteristics of IGP and EGP Routing Protocols
IGPs are used for routing within a routing domain, those networks within the control of a single organization. An autonomous system is commonly comprised of many individual networks belonging to companies, schools, and other institutions. An IGP is used to route within the autonomous system, and also used to route within the individual networks themselves. For example, CENIC operates an autonomous system comprised of California schools, colleges and universities. CENIC uses an IGP to route within its autonomous system in order to interconnect all of these institutions. Each of the educational institutions also uses an IGP of their own choosing to route within its own individual network. The IGP used by each entity provides best path determination within its own routing domains, just as the IGP used by CENIC provides best path routes within the autonomous system itself. IGPs for IP include RIP, IGRP, EIGRP, OSPF, and IS-IS.

Routing protocols, and more specifically the algorithm used by that routing protocol, use a metric to determine the best path to a network. The metric used by the routing protocol RIP is hop count, which is the number of routers that a packet must traverse in reaching another network. OSPF uses bandwidth to determine the shortest path.

EGPs on the other hand, are designed for use between different autonomous systems that are under the control of different administrations. BGP is the only currently-viable EGP and is the routing protocol used by the Internet. BGP is a path vector protocol that can use many different attributes to measure routes. At the ISP level, there are often more important issues than just choosing the fastest path. BGP is typically used between ISPs and sometimes between a company and an ISP. BGP is not part of this course or CCNA; it is covered in CCNP.

 

IGP

An interior gateway protocol (IGP) is a routing protocol that is used to exchange routing information within an autonomous system (AS).

In contrast, an Exterior Gateway Protocol (EGP) is for determining network reachability between autonomous systems and makes use of IGPs to resolve routes within an AS.

The interior gateway protocols can be divided into two categories: 1) Distance-vector routing protocol and 2) Link-state routing protocol.


Type of Interior gateway protocols
Distance-vector routing protocol
Distance-vector routing protocols use the Bellman-Ford algorithm. In these protocols, each router does not possess information about the full network topology. It advertises its distance value (DV) calculated to other routers and receives similar advertisements from other routers unless changes are done in local network or by neighbours (Routers). Using these routing advertisements each router populates its routing table. In the next advertisement cycle, a router advertises updated information from its routing table. This process continues until the routing tables of each router converge to stable values.

Some of these protocols have the disadvantage of slow convergence.

Some examples of Distance Vector routing protocol are:

• Routing Information Protocol (RIP)
• Routing Information Protocol Version 2 (RIP)
• Interior Gateway Routing Protocol (IGRP)

Link-state routing protocol
In the case of Link-state routing protocols, each router possesses information about the complete network topology. Each router then independently calculates the best next hop from it for every possible destination in the network using local information of the topology. The collection of best next hops forms the routing table.

This contrasts with distance-vector routing protocols, which work by having each node share its routing table with its neighbors. In a link-state protocol, the only information passed between the nodes is information used to construct the connectivity maps.

Some examples of Link-State routing protocol are:

• Open Shortest Path First (OSPF)
• Intermediate system to intermediate system (IS-IS)

Hybrid routing protocol
Hybrid routing protocols have both the features of distance vector routing protocols & linked state routing protocols. An example of this protocol is EIGRP.


EGP
The Exterior Gateway Protocol (EGP) is a now obsolete routing protocol for the Internet originally specified in 1982 by Eric C. Rosen of Bolt, Beranek and Newman, and David L. Mills. It was first described in RFC 827 and formally specified in RFC 904 (1984). Not to be confused with exterior gateway protocols in general (of which EGP and Border Gateway Protocol (BGP) are examples), EGP is a simple reachability protocol, and, unlike modern distance-vector and path-vector protocols, it is limited to tree-like topologies.

During the early days of the Internet, EGP version 3 (EGP3) was used to interconnect autonomous systems. Currently, BGP version 4 is the accepted standard for Internet routing and has essentially replaced the more limited EGP3.

OSPF

Open Shortest Path First (OSPF) is a routing protocol developed for Internet Protocol (IP) networks by the Interior Gateway Protocol (IGP) working group of the Internet Engineering Task Force (IETF). The working group was formed in 1988 to design an IGP based on the Shortest Path First (SPF) algorithm for use in the Internet. Similar to the Interior Gateway Routing Protocol (IGRP), OSPF was created because in the mid-1980s, the Routing Information Protocol (RIP) was increasingly incapable of serving large, heterogeneous internetworks.

Background

OSPF was derived from several research efforts, including Bolt, Beranek, and Newman's (BBN's) SPF algorithm developed in 1978 for the ARPANET (a landmark packet-switching network developed in the early 1970s by BBN), Dr. Radia Perlman's research on fault-tolerant broadcasting of routing information (1988), BBN's work on area routing (1986), and an early version of OSI's Intermediate System-to-Intermediate System (IS-IS) routing protocol.

OSPF has two primary characteristics. The first is that the protocol is open, which means that its specification is in the public domain. The OSPF specification is published as Request For Comments (RFC) 1247. The second principal characteristic is that OSPF is based on the SPF algorithm, which sometimes is referred to as the Dijkstra algorithm, named for the person credited with its creation.

OSPF is a link-state routing protocol that calls for the sending of link-state advertisements (LSAs) to all other routers within the same hierarchical area. Information on attached interfaces, metrics used, and other variables is included in OSPF LSAs. As OSPF routers accumulate link-state information, they use the SPF algorithm to calculate the shortest path to each node.

As a link-state routing protocol, OSPF contrasts with RIP and IGRP, which are distance-vector routing protocols. Routers running the distance-vector algorithm send all or a portion of their routing tables in routing-update messages to their neighbors.

Routing Hierarchy

Unlike RIP, OSPF can operate within a hierarchy. The largest entity within the hierarchy is the autonomous system (AS), which is a collection of networks under a common administration that share a common routing strategy. OSPF is an intra-AS (interior gateway) routing protocol, although it is capable of receiving routes from and sending routes to other ASs.

An AS can be divided into a number of areas, which are groups of contiguous networks and attached hosts. Routers with multiple interfaces can participate in multiple areas. These routers, which are called Area Border Routers, maintain separate topological databases for each area.

A topological database is essentially an overall picture of networks in relationship to routers. The topological database contains the collection of LSAs received from all routers in the same area. Because routers within the same area share the same information, they have identical topological databases.

The term domain sometimes is used to describe a portion of the network in which all routers have identical topological databases. Domain is frequently used interchangeably with AS.

An area's topology is invisible to entities outside the area. By keeping area topologies separate, OSPF passes less routing traffic than it would if the AS were not partitioned.

Area partitioning creates two different types of OSPF routing, depending on whether the source and the destination are in the same or different areas. Intra-area routing occurs when the source and destination are in the same area; interarea routing occurs when they are in different areas.

An OSPF backbone is responsible for distributing routing information between areas. It consists of all Area Border Routers, networks not wholly contained in any area, and their attached routers.

In the figure, routers 4, 5, 6, 10, 11, and 12 make up the backbone. If Host H1 in Area 3 wants to send a packet to Host H2 in Area 2, the packet is sent to Router 13, which forwards the packet to Router 12, which sends the packet to Router 11. Router 11 then forwards the packet along the backbone to Area Border Router 10, which sends the packet through two intra-area routers (Router 9 and Router 7) to be forwarded to Host H2.

The backbone itself is an OSPF area, so all backbone routers use the same procedures and algorithms to maintain routing information within the backbone that any area router would. The backbone topology is invisible to all intra-area routers, as are individual area topologies to the backbone.

Areas can be defined in such a way that the backbone is not contiguous. In this case, backbone connectivity must be restored through virtual links. Virtual links are configured between any backbone routers that share a link to a nonbackbone area and function as if they were direct links.

Figure shows an example of an internetwork with several areas.

Figure: An OSPF AS Consists of Multiple Areas Linked by Routers

AS border routers running OSPF learn about exterior routes through exterior gateway protocols (EGPs), such as Exterior Gateway Protocol (EGP) or Border Gateway Protocol (BGP), or through configuration information. For more information about these protocols.

SPF Algorithm

The Shortest Path First (SPF) routing algorithm is the basis for OSPF operations. When an SPF router is powered up, it initializes its routing-protocol data structures and then waits for indications from lower-layer protocols that its interfaces are functional.

After a router is assured that its interfaces are functioning, it uses the OSPF Hello protocol to acquire neighbors, which are routers with interfaces to a common network. The router sends hello packets to its neighbors and receives their hello packets. In addition to helping acquire neighbors, hello packets also act as keepalives to let routers know that other routers are still functional.

On multiaccess networks (networks supporting more than two routers), the Hello protocol elects a designated router and a backup designated router. Among other things, the designated router is responsible for generating LSAs for the entire multiaccess network. Designated routers allow a reduction in network traffic and in the size of the topological database.

When the link-state databases of two neighboring routers are synchronized, the routers are said to be adjacent. On multiaccess networks, the designated router determines which routers should become adjacent. Topological databases are synchronized between pairs of adjacent routers. Adjacencies control the distribution of routing-protocol packets, which are sent and received only on adjacencies.

Each router periodically sends an LSA to provide information on a router's adjacencies or to inform others when a router's state changes. By comparing established adjacencies to link states, failed routers can be detected quickly, and the network's topology can be altered appropriately. From the topological database generated from LSAs, each router calculates a shortest-path tree, with itself as root. The shortest-path tree, in turn, yields a routing table.

Packet Format

All OSPF packets begin with a 24-byte header, as illustrated in Figure.

Figure: OSPF Packets Consist of Nine Fields

The following descriptions summarize the header fields:

• Version number - Identifies the OSPF version used.
• Type - Identifies the OSPF packet type as one of the following:
  • Hello - Establishes and maintains neighbor relationships.
  • Database description - Describes the contents of the topological database. These messages are exchanged when an adjacency is initialized.
  • Link-state request - Requests pieces of the topological database from neighbor routers. These messages are exchanged after a router discovers (by examining database-description packets) that parts of its topological database are outdated.
  • Link-state update - Responds to a link-state request packet. These messages also are used for the regular dispersal of LSAs. Several LSAs can be included within a single link-state update packet.
  • Link-state acknowledgment - Acknowledges link-state update packets.
• Packet length - Specifies the packet length, including the OSPF header, in bytes.
• Router ID - Identifies the source of the packet.
• Area ID - Identifies the area to which the packet belongs. All OSPF packets are associated with a single area.
• Checksum - Checks the entire packet contents for any damage suffered in transit.
• Authentication type - Contains the authentication type. All OSPF protocol exchanges are authenticated. The authentication type is configurable on per-area basis.
• Authentication - Contains authentication information.
• Data - Contains encapsulated upper-layer information.