TCP/IP-II:OSPF Link State Update

OSPF Link State Update

• In response to LS request or trigger router will send new LS info trigger, using the LS update message
• Contents are composed of link state advertisements (LSA’s)
• LS update message is acknowledged using LS ack pkt to ensure that the flooding algorithm is reliable; Link state acknowledgement packets consist of a list of LSA headers.

BGP (Border Gateway Protocol):

• The de facto standard for inter-AS routing,
• BGP: glues the whole Internet together
•  Path Vector protocol Uses TCP (service port: 179)
• Similar to Distance Vector protocol. Each Border Gateway broadcast to neighbors (peers) entire path (i.e., sequence of AS’s) to destination
• BGP is an exterior gateway protocol (EGP), which means that it performs routing between multiple autonomous systems or domains and exchanges routing and reachability information with other BGP systems.
• The information exchanged among BGP routers allow a router to construct a graph of AS’s and each AS is identified by Autonomous System Number (ASN).
• BGP routes to networks (ASs), not individual hosts
• BGP messages exchanged using TCP and BGP messages are:

o OPEN: opens TCP connection to peer and authenticates sender

o UPDATE: advertises new path (or withdraws old)

o KEEPALIVE keeps connection alive in absence of UPDATES; also ACKs OPEN request

o NOTIFICATION: reports errors in previous msg; also used to close connection

• Session is established between two BGP speakers to exchange information regarding

- New active routes

- Old inactive routers or

- To report error conditions

Open Message Format

• BGP open messages are comprised of a BGP header and additional fields.
• The below figure illustrates the additional fields used in BGP open messages.

BGP Open Message Fields

BGP packets in which the type field in the header identifies the packet to be a BGP open

message packet include the following fields. These fields provide the exchange criteria for two BGP routers to establish a peer relationship.

• Version—Provides the BGP version number so that the recipient can determine whether it is running the same version as the sender.

• Autonomous System—Provides the autonomous system number of the sender.

• Hold-Time—Indicates the maximum number of seconds that can elapse without receipt of a message before the transmitter is assumed to be nonfunctional.

• BGP Identifier—Provides the BGP identifier of the sender (an IP address), which is determined at startup and is identical for all local interfaces and all BGP peers.

• Optional Parameters Length—Indicates the length of the optional parameters field (if present).

• Optional Parameters—Contains a list of optional parameters (if any). Only one optional parameter type is currently defined: authentication information.

Authentication information consists of the following two fields:

— Authentication code: Indicates the type of authentication being used.

Authentication data: Contains data used by the authentication mechanism (if used).

Update Message Format

BGP update messages are comprised of a BGP header and additional fields.

The below figure illustrates the additional fields used in BGP update messages.

BGP Update Message Fields

BGP packets in which the type field in the header identifies the packet to be a BGP update

message packet include the following fields. Upon receiving an update message packet, routers will be able to add or delete specific entries from their routing tables to ensure accuracy. Update messages consist of the following fields:

• Unfeasible Routes Length—Indicates the total length of the withdrawn routes field or that the field is not present.

• Withdrawn Routes—Contains a list of IP address prefixes for routes being withdrawn from service.

• Total Path Attribute Length—Indicates the total length of the path attributes field or that the field is not present.

Path Attributes—Describes the characteristics of the advertised path. The following are possible attributes for a path:

— Origin: Mandatory attribute that defines the origin of the path information

— AS Path: Mandatory attribute composed of a sequence of autonomous system path segments

— Next Hop: Mandatory attribute that defines the IP address of the border router that should be used as the next hop to destinations listed in the network layer reachability information field

— Mult Exit Disc: Optional attribute used to discriminate between multiple exit points to a neighboring autonomous system

— Local Pref: Discretionary attribute used to specify the degree of preference for an advertised route

— Atomic Aggregate: Discretionary attribute used to disclose information about route selections

— Aggregator: Optional attribute that contains information about aggregate routes

• Network Layer Reachability Information—Contains a list of IP address prefixes for the advertised routes

Notification Message Format

The below figure illustrates the additional fields used in BGP notification messages.

BGP Notification Message Fields

BGP packets in which the type field in the header identifies the packet to be a BGP

notification message packet include the following fields. This packet is used to indicate some sort of error condition to the peers of the originating router.

• Error Code—Indicates the type of error that occurred. The following are the error types defined by the field:

— Message Header Error: Indicates a problem with a message header, such as unacceptable message length, unacceptable marker field value, or unacceptable message type.

— Open Message Error: Indicates a problem with an open message, such as unsupported version number, unacceptable autonomous system number or IP address, or unsupported authentication code.

— Update Message Error: Indicates a problem with an update message, such as a malformed attribute list, attribute list error, or invalid next-hop attribute.

— Hold Time Expired: Indicates that the hold-time has expired, after which time a BGP node will be considered nonfunctional.

— Finite State Machine Error: Indicates an unexpected event.

— Cease: Closes a BGP connection at the request of a BGP device in the absence of any fatal errors.

• Error Subcode—Provides more specific information about the nature of the reported error.

• Error Data—Contains data based on the error code and error subcode fields. This field is used to diagnose the reason for the notification message.

Multicast Routing

The sending of a packet from one sender to multiple receivers with a single "transmit" operation is known as multicast routing. Teleconferencing is an example which requires multicast routing.

The goal of multicast routing is to find a tree of links that connects all of the routers that have attached hosts belonging to the multicast group. Multicast packets will then be routed along this tree from the sender to all of the hosts belonging to the multicast tree.

There are many ways to generate multicast tree, MBONE is also one approach to generate multicast tree. The Internet Multicast Backbone (MBone) is an interconnected set of subnetworks and routers that support the delivery of IP multicast traffic.

An IP multicast group is identified by a Class D address.

Figure: Multicast tree routed at source S

In the above figure, the source S wants to transmit to destinations with multicast group G1.

The source can send each copy of the packet separately to each destination by using conventional unicast routing or else a more efficient method which will reduce the number of copies

For example, when router 1 receives a packet from the source, router 1 copies the packet to router 2 and router 5 simultaneously. Upon receipt of these packets, router 2 forwards the packet to its local network, and router 5 copies the packet to router 7 and router 8. the packet will be received by each intended destinations.

RPB (Reverse Path Broadcasting)

The fundamental algorithm to construct these source-based trees is referred to as Reverse Path Broadcasting (RPB).

The RPB operation is very simple.

For each source, if a packet arrives on a link that the local router believes to be on the shortest path back toward the packet's source, then the router forwards the packet on all interfaces except the incoming interface.

If the packet does not arrive on the interface that is on the shortest path back toward the source, then the packet is discarded.

The interface over which the router expects to receive multicast packets from a particular source is referred to as the "parent" link.

The outbound links over which the router forwards the multicast packet are called "child" links for this source.

v The key benefit to reverse path broadcasting is that it is reasonably efficient and easy to implement.

v It does not require that the router know about the entire spanning tree, nor does it require a special mechanism to stop the forwarding process (as flooding does).

v In addition, it guarantees efficient delivery since multicast packets always follow the "shortest" path from the source station to the destination group.

v Finally, the packets are distributed over multiple links, resulting in better network utilization since a different tree is computed for each source.

v One of the major limitations of the RPB algorithm is that it does not take into account multicast group membership when building the delivery

TRPB

Truncated Reverse Path Broadcasting (TRPB) was developed to overcome the limitations of Reverse Path Broadcasting.

With information provided by IGMP, multicast routers determine the group memberships on each leaf subnetwork and avoid forwarding datagrams onto a leaf subnetwork if it does not contain at least one member of a given destination group. Thus, the delivery tree is "truncated" by the router if a leaf subnetwork has no group members.

RPM (Reverse Path Multicasting)

Reverse Path Multicasting (RPM) is an enhancement to Reverse Path Broadcasting and

Truncated Reverse Path Broadcasting. RPM creates a delivery tree that spans only

1) subnetworks with group members, and

2) routers and subnetworks along the shortest path to those subnetworks.

RPM allows the source-based "shortest-path" tree to be "pruned" so that datagrams are only forwarded along branches that lead to active members of the destination group.

When a multicast router receives a packet for a (source, group) pair, the first packet is forwarded following the TRPB algorithm across all routers in the internetwork.

Routers on the edge of the network (which have only leaf subnetworks) are called leaf routers.

The TRPB algorithm guarantees that each leaf router will receive at least the first multicast packet.

If there is a group member on one of its leaf subnetworks, a leaf router forwards the packet based on this group membership information.

If none of the subnetworks connected to the leaf router contain group members, the leaf router may transmit a "prune" message on its parent link, informing the upstream router that it should not forward packets for this particular (source, group) pair on the child interface on which it received the prune message.

Prune messages are sent just one hop back toward the source.

An upstream router receiving a prune message is required to store the prune information in memory.

If the upstream router has no recipients on local leaf subnetworks and has received prune messages from each downstream neighbor on each of the child interfaces for this (source, group) pair, then the upstream router does not need to receive any more packets for this (source, group) pair.

Therefore, the upstream router can also generate a prune message of its own, one hop further back toward the source.

A host may later decide to join a multicast group after a prune message has been sent by its leaf router. In this case the leaf router may send graft message to its upstream router to cancel its earlier prune message

The above figure shows the graft message flow when a host attached to router 6 wants to join the group.

Subsequently, router 1 will forward the multicast packets to router 4, which will forward the multicast packets to router 6. then the multicast packets arrive at the host.

DVRMP

The first multicast routing protocol used in the Internet and the most widely supported multicast routing algorithm is the distance vector multicast routing protocol (DVMRP) DVMRP implements source-based trees with reverse path forwarding, pruning, and grafting.

DVMRP is based on combination of RIP and RPM.

DVMRP uses a distance vector algorithm that allows each router to compute the outgoing link (next hop) that is on its shortest path back to each possible source.

This information is then used in the RPF algorithm.

In addition to computing next hop information, DVMRP also computes a list of dependent downstream routers for pruning purposes.

When a router has received a prune message from all of its dependent downstream routers for a given group, it will propagate a prune message upstream to the router from which it receives its multicast traffic for that group.

A DVMRP prune message contains a prune lifetime (with a default value of two hours) that indicates how long a pruned branch will remain pruned before being automatically restored.

DVMRP graft messages are sent by a router to its upstream neighbor to force a previously-pruned branch to be added back on to the multicast tree.

IGMP (Internet Group Management Protocol)

The (IGMP) runs between hosts and their immediately-neighboring multicast routers.

The mechanisms of the protocol allow a host to inform its local router that it wishes to receive transmissions addressed to a specific multicast group. Also, routers periodically query the LAN to determine if any group members are still active.

If there is more than one IP multicast router on the LAN, one of the routers is elected "querier" and assumes the responsibility of querying the LAN for the presence of any group members.

Based on the group membership information learned from the IGMP, a router is able to determine which (if any) multicast traffic needs to be forwarded to each of its "leaf" subnetworks.

"Leaf" subnetworks are those that have no further downstream routers; they either contain receivers for some set of groups, or they do not.

Multicast routers use the information derived from IGMP, along with a multicast routing protocol, to support IP multicasting across the MBone.

Version: This field identifies the version number

Type: This field identifies the message type. There are two message types, type1 indicates a query message sent by router and type 2 indicates a report sent by host

Unused: This field must be set to zero.

Checksum: This field contains checksum for all eight bytes of IGMP message

Group Address: This address is the class D IPV4 address. This field is set to zero in a query message and is set to a valid group address in the response.

Multicast routers periodically transmit Host Membership Query messages to determine which host groups have members on their directly-attached networks.