IP Networks - Unicast Routing (RIP, OSPF, BGP)

Internet Routing

Routing in the Internet

• The Internet consists of Autonomous Systems (AS) interconnected with each other.
• AS is a group of networks and routers under the authority of a single administration.
• Two-level routing:
  • Interior routing / Intra-domain routing (Intra-AS)
    • administrator responsible for choice of routing algorithm within network
  • Exterior routing / Inter-domain routing (Inter-AS)
    • routing between AS

Intra-domain routing protocols

• Routing Information Protocol (RIP) – based on distance-vector routing (RFC 1058)
• Open Shortest Path First (OSPF) – based on link-state routing (RFC 2328)

Inter-domain routing protocols

• Border Gateway Protocol Version 4 (BGP4) – based on path-vector routing (RFC 1772, RFC 1773)

---

Intra-domain Routing - RIP

based on distance-vector routing

The Routing Information Protocol (RIP) is an intradomain (interior) routing protocol used inside an autonomous system.

• a very simple protocol based on distance vector routing*.*
• The metric used by RIP is the number of links (networks) that have to be used to reach the destination, or hop count.

Distance Vector Routing

General idea of Distance-Vector Routing

• Each node creates its own incomplete least-cost tree based on its immediate neighbors

• Exchange the incomplete tree betweenn immediate neighbors to build its own least-cost tree

• It uses Bellman-Ford algorithm to find the least-cost tree.

Example:

When a node is booted, it can only get the neighbors node information to create a initial distance vector. (e.g. A can only see B and D when booted, the initial distance vector only contain B,D and itself.)

After each node has created its initial vector, it send a copy of the vector to all its neighbors.

Then the distance vector is updated. After some changes, the complete distance vector is formed. Eventually, each node finds its least cost to other nodes.

Drawback of Distance Vector Routing:

• Decrease in cost propagate quickly
• Increase in cost propagate slowly
  • This problem is called “Count to infinity”.

Two-nodes Instability

Defining Infinity

• Most implementations define 16 as infinity

To solve this problem, people proposed different solution:

• Split Horizon
  • Instead of flooding the table through each interface, each node sends only part of its table through each interface
  • Do not send routes back over the same interface from which the route arrived
    • Will not send this entry to the router R if the next hop is that router R
    • So A will never update in above example

Split Horizon

• The idea is that when a node sends a routing update to its neighbors, it does not send those routes it learned from each neighbor back to that neighbor.

If Router B publish to Router C,

Router B wont publish the info that used Router C as next hop.

“I dont send you this value; what I know about this route comes from you.”

• Split Horizon and Poison Reverse
  • One drawback of Split Horizon
    • Normally, the DV protocol uses a timer and if there is no news about a route, the node deletes the route from its table
    • In the previous e.g., node A cannot guess that this is due to split horizon or because B has not received any news about X recently
  • Poison Reverse
    • Node B can still advertise the value for X, but if the source of information is A, it can replace the distance with infinity as a warning: “Do not use this value; what I know about this route comes from you.”

Poison Reverse

• a stronger variation of split horizon. The idea is that when a node sends a routing update to its neighbors, it actually sends those routes it learned from each neighbor back to that neighbor, but it puts negative information (inf) in the route to ensure that the route will not be used.

If Router B publish to Router C,

Router B will publish the info that used Router C as next hop as infinity.

“Do not use this value; what I know about this route comes from you.”

But they still cant solve the problem well.

Three-nodes Instability

RIP Operation

• RIP Protocol will share configured routes in network through the broadcasts. These broadcasts are known as routing updates. Listening routers will update their routing table based on these updates.
• RIP broadcasts routing updates in every 30 seconds, regardless something in network has changed or not. Once 30 seconds expires, routers running RIP protocol will broadcast their routing information to any devices connected to their interfaces.
• While sending broadcasts RIP does not care about who listens these broadcast updates or not.
• After sending broadcast RIP does not care whether neighbors received these broadcast updates or not.
• When router receives routing updates, it compares them with the routes which it already has in its routing table.
• If update has information about a route which is not available in its routing table, router will consider that route as a new route.
• Router will add all new routes in routing table before updating existing one.

RIP Message Format

• RIP runs at the application layer with port number 520.
• RIP messages are encapsulated inside UDP user datagrams, which are encapsulated inside IP datagrams

Message Format

Top header = 4 bytes

1 Entry = 20 bytes

The general formula can be given as follows:

Number of bytes in the message = 4 + (20 × N)

N is the number of advertised networks.

A RIP message that advertises a single network (N = 1) would be 24 bytes.

RIP Messages

Request

• A request message is sent by a router that has just come up or by a router that has some time-out entries
• A request can ask about specific entries or all entries

Response

• A response can be either solicited or unsolicited (30s or when there is a change in the routing table)
  • A solicited response is sent only in answer to a request. It contains information about the destination specified in the corresponding request.
  • An unsolicited response, on the other hand, is sent periodically, every 30 seconds or when there is a change in the routing table. The response is sometimes called an update packet.

RIP Timers

• Periodic timer (one for each router)
  • control advertising of regular update messages (25-35 sec)
• Expiration timer (one for each entry in a router)
  • setup when there is a new entry
  • governs the validity of a route (180 sec)
    • Every time an update (on a 30 sec average) is received the timer is reset
    • If no update received within this timer the metric is set to 16 (infinity)
• Garbager timer (one for each invalid route)
  • setup when Expiration timer timesout
  • delete the entry after timeout (120 sec)
    • A route can be advertised with a 16 metric for 120 sec before it get purged
      • Allow neighbors to have knowledge of the invalidity of a route

Example of RIP

• The message is prepared with the combination of split horizon and poison reverse strategy.
• Router R1 has obtained information about networks 195.2.4.0, 195.2.5.0, and 195.2.6.0 from router R2.
• When R1 sends an update message to R2, it replaces the actual value of the hop counts for these three networks with 16 (infinity) to prevent any confusion for R2.
• Router R2 uses message from R1 (130.10.02) as the source address of the IP datagram carrying the RIP the next hop address.
• Router R2 also increments each hop count by 1 because the values in the message are relative to R1, not R2.

Summary of RIP

Advantages of RIP

• easy to implement
• generally available
• Implementations have been rigorously tested
• simple to configure
• has little overhead (for small networks)
• RIP is also often used as a simple “glue” between two routing domains
  • Two different realms running different protocols may need a simple one-hop export/import protocol. RIP is ideal for that.

Disadvantages of RIP

• Slow convergence
  • Changes propagate slowly
  • Each neighbor only speaks ~every 30 seconds; information propagation time over several hops is long
• Instability
  • After a router or link failure RIP takes minutes to stabilize.
• Can only use hops count as metric.
• The maximum useful metric value is 15
  • Network diameter is limited to 15.
• RIP uses lots of bandwidth
  • It sends the whole routing table in updates.

Intra-domain Routing - OSPF

based on link state routing

Open Shortest Path First (OSPF) is an intradomain routing protocol based on the link-state algorithm.

Each link can be assigned a weight based on the throughput, round-trip time, reliability, …

Cost in OSPF

$$\text{Cost} = \frac{\text{reference bandwidth}}{\text{interface bandwidth}} = \frac{\text{100,000,000 bps}}{\text{interface bandwidth}}$$

Default reference bandwidth is $10^8$ (100 Mbps)

Link State Routing

Each node in the domain has the entire topology of the domain, the node can use the Dijkstra algorithm to build a routing table.

• Each node collect the cost of its connecting links
• Send its table to all other nodes

Building routing tables:

Creation of the states of the links by each node, called the link state packet or LSP.

• LSP Generation
  • When there is a change in the topology of the domain
  • On a periodic basis: There is no actual need for this type of LSP, normally 60 minutes or 2 hours
• Dissemination of LSPs to every other router, called flooding, in an efficient and reliable way.
• Formation of a shortest path tree for each node.
• Calculation of a routing table based on the shortest path tree.

• Each node collect the cost of its connecting links
• Send its table to all other nodes through flooding

Flooding of LSPs:

• The creating node sends a copy of the LSP out of each interface.
• A node that receives an LSP compares it with the copy it may already have. If the newly arrived LSP is older than the one it has (found by checking the sequence number), it discards the LSP. If it is newer, the node does the following:
  • It discards the old LSP and keeps the new one.
  • It sends a copy of it out of each interface except the one from which the packet arrived. This guarantees that flooding stops somewhere in the domain (where a node has only one interface).

The nodes send its table to all other nodes through adj.nodes until every node can see the whole topology. (i.e. Each node has a gloabal picture about the network)

A Link state database (LSDB) is formed.

From the link state database we can draw the weighted graph topology.

Each node will then create a least-cost tree using the shortest path algorithm.

• Each node creates its own least-cost tree from the LSDB

Then from this link state database we can make use of Dijkstra Algorithm to determine the Shortest Path Tree.

• Dijkstra Algorithm
• 1- The node choose itself as the root
• 2- Select one node, among all nodes not in the tree, which is closest to the root, and adds this to the tree.
• 3- After this new node is added to the tree, the cost of all other nodes not in the tree needs to be updated
• 4- Repeat step 2 and step 3 until all nodes are added to the tree

Distance vector routing VS Link state routing:

Distance Vector:

• View network topology from neighbors perspective
• Add distance vectors from router to router
• Frequent, periodic updates: Slow convergence
• Pass copies of routing tables to neighbor routers

Link State:

• Get common view of entire network topology
• Calculate the shortest path to other routers
• Event-triggered updates: Faster convergence
• Pass link state routing updates to all other routers

Link-State Operation of OSPF

OSPF Routers Exchange Packets - These packets are used to discover neighboring routers and also to exchange routing information to maintain accurate information about the network.

The exchange packets:

• Hello packets
• Database Description packets
• Link-state request packets
• Link-state update packets
• Link-state acknowledgment packets

Hello Packets

If a neighbor is present, the OSPF- enabled router attempts to establish a neighbor adjacency with that neighbor

• Whenever a router is setup, the route will send hello packets through every interfaces
• Other routers will reply and build up a neighbor relationship

Link-State Advertisement (LSA)

Use flooding to reach every routers

• LSAs contain the state and cost of each directly connected link.
• Routers flood their LSAs to adjacent neighbors.
• Adjacent neighbors receiving the LSA immediately flood the LSA to other directly connected neighbors, until all routers in the area have all LSAs.

Link State Database (LSDB)

• Build the topology table based on the received LSAs.
• This database eventually holds all the information about the topology of the network.
• Execute the SPF Algorithm.

From the SPF tree, the best paths are inserted into the routing table.

Area in OSPF

• A collection of networks with area ID
• Routers inside an area flood the area with routing information
• Area border routers summarize the information about the area and send it to other areas
• Backbone area and backbone routers
  • All of the area inside an AS must be connected to the backbone

Single-Area OSPF

• Area 0 is also called the backbone area
• Single-area OSPF is useful inn smaller networks with few routers

Multiarea OSPF

• Area 0 is also called the backbone area
• Implemented using a two-layer area hierarchy as all areas must connect to the backbone area (area 0)
• Interconnecting routers are called Area Border Routers (ABR).
• Useful in larger network deployments to reduce processing and memory overhead

• Link failure affects the local area only (area 51)
• The ABR (R2) isolates the fault to area 51 only
• Routers in area 0 and 1 do not need to run the SPF algorithm
• Only area 51 need to run SPF algorithm again

Types of Link in OSPF

In OSPF, we define different links and use them depends on the formation of network

Types of links:

• Point-to-point link
• Transient link
• Stub link
• Virtual link

Point-to-Point Link

A point-to-point link connects two routers without any other host or router in between.

• Direct link

Transient Link

A transient link is a network with several routers attached to it.

• To show that each router is connected to every other router through one single network, the network itself is represented by a node. However, because a network is not a machine, it cannot function as a router.
• One of the routers in the network takes this responsibility. It is assigned a dual purpose; it is a true router and a designated router.

figure b is not needed, we use figure c topology instead.

Stub Link

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.
• This is a special case of the transient network.

Virtual Link

When the link between two routers is broken, the administration may create a virtual link between them using a longer path that probably goes through several routers.

• Used for network maintainance

OSPF Operational States

When an OSPF router is initially connected to a network, it attempts to:

• Create adjacencies with neighbors
• Exchange routing information
• Calculate the best routes
• Reach convergence
• OSPF progresses through several states while attempting to reach convergence.

Establish Neighbor Adjacencies

Down State and Init State

Two-way state

Synchronizing OSPF Database

ExStart State

Exchange State

Types of OSPF Packets

• Hello

  • The hello message (type 1) is used by a router to introduce itself to neighboring routers and to introduce already-known neighboring routers to other neighbors.

• Data description

  • The data description message (type 2) is sent in response to a hello message. A router sends its full LSDB to the newly joined router.

• Link-state request

  • The link-state request message (type 3) is sent by a router that needs information about a specific LS.

• Link-state update

  • The link-state update message (type 4) is sent by a router to other routers for building the LSDB. There are five different versions of this message to announce different link states.

• Link state acknowledgement

  • The link-state acknowledge message (type 5) is sent by a router to announce the receiving of a link-state update message. This message is used to provide reliability for the main message used in OSFP.

OSPF packet will be encapsulated in the IP datagram and send over the IP network.

Common OSPF Packet Header

• Version: Currently it is version 2.
• Type: This 8-bit field defines the type of the packet.
• Message length: The length of the total message including the header.
• Source router IP address: The IP address of the router that sends the packet.
• Area identification: The area within which the routing takes place.
• Checksum: Error detection on the entire packet excluding the authentication type and authentication data field.
• Authentication type: 0 for none and 1 for password.
• Authentication: For now, if the authentication type is 0, this field is filled with 0s. If the type is 1, this field carries an eight-character password.

Packet Type - Hello Packet

• Discover OSPF neighbors and establish neighbor adjacencies.
  Advertise parameters on which two routers must agree to become neighbors.
• Elect the Designated Router (DR) and Backup Designated Router (BDR) on multiaccess networks (Transient link) like Ethernet and Frame Relay.
• Once neighborship is built same hello packets are used to maintain the neighborship.
• Hello packets contain all necessary information that is required to form a neighborship.
• Hello packets are generated and distributed in hello interval via multicast.

• Network mask:
• Hello interval: This 16-bit field defines the number of seconds between hello messages (10 seconds by default).
• E flag: When it is set, it means that the area is a stub area.
• T flag: When it is set, it means that the router supports multiple metrics.
• Priority: This field defines the priority of the router.
• Dead interval: This 32-bit field defines the number of seconds that must pass before a router assumes that a neighbor is dead. Default dead interval is 40 seconds.
• Designated router IP address: This 32-bit field is the IP address of the designated router for the network over which the message is sent.
• Backup designated router IP address: This 32-bit field is the IP address of the backup designated router for the network over which the message is sent.
• Neighbor IP address: It is a current list of all the neighbors from which the sending router has received the hello message.

Packet Type - Database Description Packet

When a router is connected to the system for the first time or after a failure, it needs the complete link state database immediately. Therefore, it sends hello packets to greet its neighbors. If this is the first time that the neighbors hear from the router, they send a database description message.

• The database description packet does not contain complete database information; it only gives an outline, the title of each lines in the database.

Packet Type - Link State Request Packet

This is a packet that is sent by a router that needs information about a specific route or routes.

• It is answered with a link state update packet.
• It can be used by a newly connected router to request more information about some routes after receiving the database description packet.

Packet Type - Link State Update Packet

• It is used by a router to advertise the states of its links.
• Each update packet may contain several different LSAs (Link State Advertisement).

LSA General Header

• Link state age : This field indicates the number of seconds elapsed since this message was first generated.
  • When a router creates the message, the value of this field is 0.
  • When each successive router forwards this message, it estimates the transit time and adds it to the cumulative value of this field.
• E flag: If this 1-bit flag is set to 1, it means that the area is a stub area. A stub area is an area that is connected to the backbone area by only one path.
• T flag: If this 1-bit flag is set to 1, it means that the router can handle multiple types of service.
• Link state type: There are five different advertisement types.
• Link state ID: The value of this field depends on the type of link.
  • For type 1 (router link), it is the IP address of the router.
  • For type 2 (network link), it is the IP address of the designated router.
  • For type 3 (summary link to network), it is the address of the network.
  • For type 4 (summary link to AS boundary router), it is the IP address of the AS boundary router.
  • For type 5 (external link), it is the address of the external network.
• Advertising router: This is the IP address of the router advertising this message.
• Link state sequence number: This is a sequence number assigned to each link state update message.
• Link state checksum: It is calculated based on the whole packet except for the age field.
• Length: This defines the length of the whole packet in bytes.

Router Link LSA

• A router link defines the links of a true router.
  • How it link up with other devices (point-to-point? Transient? Stub? Virtual?)
• A true router uses this advertisement to announce information about all of its links and what is at the other side of the link (neighbors).
• The router link LSA advertises all of the links of a router (true router)

• Link ID: The value of this field depends on the type of link.
• Link data: This field gives additional information about the link.
  • the value depends on the type of the link.
• Link Type:

• Number of types of service (TOS): This field defines the number of types of services announced for each link.
• Metric for TOS 0: This field defines the metric for the default type of service (TOS 0).
• TOS: This field defines the type of service.
• Metric: This field defines the metric for the corresponding TOS.

Example of Router Link LSA:

Network Link LSA

• A network link defines the links of a network.
• A designated router, on behalf of the transient network, distributes this type of LSP packet.
• The packet announces the existence of all of the routers connected to the network

• Network mask: This field defines the network mask.
• Attached router: This repeated field defines the IP addresses of all attached routers.

Example of Network Link LSA:

Summary Link to Network LSA

• Router link and network link advertisements flood the area with information about the router links and network links inside an area.
• But a router must also know about the networks outside its area; the area border routers can provide this information.
• An area border router is active in more than one area. It receives router link and network link advertisements, and, creates a routing table for each area.

• The summary link to network LSA is used by the area border router to announce the existence of other networks outside the area.
• It consists of the network mask and the metric for each type of service.
• Each advertisement announces only one single network. If there is more than one network, a separate advertisement must be issued for each.

Summary Link to AS Boundary Router LSA

• If a router inside an area wants to send a packet outside the AS, it should first know the route to an autonomous boundary router; the summary link to AS boundary router provides this information.
• The area border routers flood their areas with this information

• This packet is used to announce the route to an AS boundary router.
• Its format is the same as the previous summary link.

External Link LSA

• A router inside an AS wants to know which networks are available outside the AS; the external link advertisement provides this information.
• The AS boundary router floods the autonomous system with the cost of each network outside the autonomous system using a routing table created by an interdomain routing protocol.

• Each advertisement announces one single network. If there is more than one network, separate announcements are made.
• The AS boundary router may define a forwarding router that can provide a better route to the destination.
• The packet also can include an external route tag, used by other protocols, but not by OSPF.

Packet Type - Link State Acknowledgement Packet

• OSPF makes routing more reliable by forcing every router to acknowledge the receipt of every link state update packet.

Acknowledgement packet:

Summary of OSPF

• Divide into 2 level, single and multiple area

• Flooding occur in each area

• When the router is setup, it first build up neighbor information

• then send the link state information to others using LSA (Link-State Advertisement)

---

Inter-domain Routing - BGP

Border Gateway Protocol is a standardized exterior gateway protocol designed to exchange routing and reachability information among autonomous systems on the Internet.

Path-Vector Routing

Unlike link-state and distance-vector routing, path-vector routing is not based on the least-cost goal

• Based on the policy decided by Admin
  • E.g. Use minimum number of nodes to reach a destination and does not pass through node X as a middle node

It Path-Vector Routing, we create Spanning Trees.

When a node is booted, it creates a path vector based on the information it can obtain about its immediate neighbor. (e.g. A can reach A through itself, or reach B through A,B)

Then Each node sends its own vector to all its immediate neighbors, and Each node updates its own path vector.

Border Gateway Protocol (BGP)

Types of AS:

• Stub AS
  • Only one connection to another AS (only a source or sink for data traffic)
• Multihomed AS
  • More than one connection to other AS, but it is still only a source or sink for data traffic
• Transit AS
  • Multihomed AS that also allows transient traffic (Internet Backbone)

There are Two variations:

• external BGP (eBGP)
  • eBGP are installed on each border router
    • Connections between two border routers are established.
• internal BGP (iBGP)
  • iBGP are installed on all routers

Example:

So after collecting these informations, the gateway router can build up a path vector.

To let other routers in the same network know the external network, the router recieved external info make use iBGP to share this formation to other routers.

• iBGP
• We need iBGP because
  • Some border router do not know how to route a packet destined for non-neighbor ASs. For example, R5 do not know how to route packets to networks in AS3 and AS4.
  • None of non-border router knows how to route a packet to other ASs.
• iBGP uses the service of TCP with port number 179 but it set up connections any possible pair of routers inside an AS.
• Then, they exchange information using the iBGP connections
• In addition, the border routers update its information to its partner using the eBGP connections

So the finalized BGP path tables will be like this:

Finally, the BGP path tables are combined with the intradomain forwarding tables

For these routers (R5 – R9)(Stub AS), only one entry is added.

BGP Operations

Open

• Establishes BGP session
• BGP uses TCP

Notification

• Report unusual conditions

Update

• Inform neighbor of new routes
• Inform neighbor of old routes that become inactive

KeepAlive

• Inform neighbor that connection is still viable

BGP Route Updates

Update Format <IP prefix: route attributes>

• Attributes describe properties of the route

Two kinds of updates

• Announcements: new routes or changes to existing routes
• Withdrawal: remove routes that no longer exist

BGP Attributes

We use the BGP Attributes to determine how to reach that particular networks.

• Advertised prefix includes BGP attributes
  • prefix + attributes = “route”
• BGP attributes are classified into the following four categories:
  • Well-known mandatory
    • All BGP implementations must recognize such an attribute and it must appear in an UPDATE message. E.g. AS- PATH, NEXT-HOP, ORIGIN.
  • Well-known discretionary
    • All BGP implementations must recognize such an attribute; however, it may not be included in an UPDATE message. E.g. LOCAL-PREF
  • Optional transitive
    • A BGP implementation might not support such an attribute, but it must forward it to its BGP peers. E.g. COMMUNITY.
  • Optional nontransitive
    • A BGP implementation might not support such an attribute; it should not forward it to its BGP peers. E.g. MED.

BGP Attributes: AS-PATH

• Carried in route announcements
• Each AS will be assigned an AS number so the path will form by linking up the AS numbers
• Path vector that lists all the ASs a route announcement has traversed (in reverse order)

Performance Concern with AS-PATH

• AS path length can be misleading
  • An AS may have many router-level hops

BGP Attributes: NEXT-HOP

• Carried in a route update message
• IP address of next hop router on path to destination
• Updated as the announcement leaves AS

BGP Attributes: LOCAL PREF

• “Local Preference”
• Used to choose between different AS paths by assigning proirity
• The higher local pref value the more preferred
• Local to an AS; carried only in iBGP messages
• Ensures consistent route selection across an AS

BGP Attributes: ORIGIN

• Records who originated the announcement
• Local to an AS
• Options:
  • “e” : from eBGP (More direct)
  • “i” : from iBGP
  • “?” : Incomplete; often used for static routes
• Typically: e > i > ?

BGP Attributes: MED

• “Multi-Exit Discriminator”
• Used when ASs are interconnected via 2 or more links to specify how close a prefix is to the link it is announced on
• Lower is better
• AS announcing prefix sets MED (AS2 in picture)
• AS receiving prefix (optionally!) uses MED to select link (AS1 in pic.)

BGP Attributes: IGP Cost

• Used for hot-potato routing

  • Each router selects the closest egress point based on the path cost in intra-domain protocol

E.g. C will select A to send

Route Selection Using Attributes

• Rules for route selection in priority order

Routing Process Overview

Import and Export Policies

• Inbound filtering controls outbound traffic
  • Filters route updates received from other peers
  • Filtering based on IP prefixes, AS_PATH, community
• Outbound Filtering controls inbound traffic
  • Forwarding a route means others may choose to reach the prefix through you
  • Not forwarding a route means others must use another router to reach the prefix
• Attribute Manipulation
  • Import: LOCAL_PREF (manipulate trust)
  • Export: AS_PATH and MEDs

AS Relationships, Export rules

• AS has customers, providers and peers
  • High level = providers, Low level = customers
  • AS at the same level = peers
• Relationships between AS pairs:
  • customer-provider
  • peer-to-peer
• Type of relationship influences policies

Exporting to provider:

• AS exports its routes & its customer’s routes, but not routes learned from other providers or peers

Exporting to peer:

• AS exports its routes & its customer’s routes, but not routes learned from other providers or peers

Exporting to customer:

• AS exports its routes plus routes learned from its providers and peers

Typical Export: Peer-Peer Case

• Peers exchange traffic between their customers
  • AS exports only customer routes to a peer
  • AS exports a peer’s routes only to its customers

Typical Export: Customer-Provider

• Customer pays provider for access to Internet
  • Provider exports its customer routes to everybody
  • Customer exports provider routes only to its customers

Types of BGP Messages

• Open
  • Establishes BGP session (uses TCP port #179)
  • BGP uses TCP
• Notification
  • Report unusual conditions
• Update
  • Inform neighbor of new routes that become active
  • Inform neighbor of old routes that become inactive
• Keepalive
  • Inform neighbor that connection is still viable