· The destinations are not hosts but instead are CIDRized prefixes.

· Each prefix represents a subnet or a collection of subnets.

4.2 Path Attributes & Routes

· An autonomous-system is identified by its globally unique ASN (Autonomous-System Number).

· The router includes a number of attributes with the prefix.

· Two important attributes: 1) AS-PATH and 2) NEXT-HOP

i. AS-PATH

a. This attribute contains the ASs through which the advertisement for the prefix has passed.

b. When a prefix is passed into an AS, the AS adds its ASN to the ASPATH attribute.

c. Routers use the AS-PATH attribute to detect and prevent looping advertisements.

d. Routers also use the AS-PATH attribute in choosing among multiple paths to the same prefix.

ii. NEXT-HOP

e. This attribute provides the critical link between the inter-AS and intra-AS routing protocols.

f. This attribute is the router-interface that begins the AS-PATH.

a. attributes which allow routers to assign preference-metrics to the routes.

b. attributes which indicate how the prefix was inserted into BGP at the origin AS.

· When a gateway-router receives a route-advertisement, the gateway-router decides

a. whether to accept or filter the route and

b. whether to set certain attributes such as the router preference metrics.

1.3 Route Selection

· For 2 or more routes to the same prefix, the following elimination-rules are invoked sequentially:

i. Routes are assigned a local preference value as one of their attributes.

ii. The local preference of a route

a. will be set by the router or

b. will be learned by another router in the same AS.

iii. From the remaining routes, the route with the shortest AS-PATH is selected.

iv. From the remaining routes, the route with the closest NEXT-HOP router is selected.

v. If more than one route still remains, the router uses BGP identifiers to select the route.

1.4 Routing Policy

· Routing policy is illustrated as shown in Figure 3.30.

· Let A, B, C, W, X & Y = six interconnected autonomous-systems. W, X & Y = three stub-networks.

a. A, B & C = three backbone provider networks.

a. All traffic leaving a stub-network must have originated in that network.

· X is a multi-homed stub-network, since X is connected to the rest of the n/w via 2 different providers

· X itself must be the source/destination of all traffic leaving/entering X.

· X will function as a stub-network if X has no paths to other destinations except itself.

· There are currently no official standards that govern how backbone ISPs route among themselves.

Fig 4.2: A simple BGP scenario

a. Center Based Approach

5.3 N-way Unicast

a. makes N copies of the packet and

b. transmits then the N copies to the N destinations using unicast routing (Figure 5.1).

i. Inefficiency

If source is connected to the n/w via single link, then N copies of packet will traverse this link.

ii. More Overhead & Complexity

An implicit assumption is that the sender knows broadcast recipients and their addresses.

Obtaining this information adds more overhead and additional complexity to a protocol.

iii. Not suitable for Unicast Routing

It is not good idea to depend on the unicast routing infrastructure to achieve broadcast.

Fig 5.1: Duplicate creation/transmission

5.4

Uncontrolled Flooding

· The source-node sends a copy of the packet to all the neighbors.

· When a node receives a broadcast-packet, the node duplicates & forwards packet to all neighbors.

· In connected-graph, a copy of the broadcast-packet is delivered to all nodes in the graph.

i. If the graph has cycles, then copies of each broadcast-packet will cycle indefinitely.

ii. When a node is connected to 2 other nodes, the node creates & forwards multiple copies of packet

The endless multiplication of broadcast-packets which will eventually make the network useless."

5.5 Controlled Flooding

· A node can avoid a broadcast-storm by judiciously choosing

· when to flood a packet and when not to flood a packet.

i. Sequence Number Controlled Flooding

A source-node: puts its address as well as a broadcast sequence-number into a broadcast-packet.

a. Each node maintains a list of the source-address & sequence # of each broadcast-packet.

b. When a node receives a broadcast-packet, the node checks whether the packet is in this list.

c. If so, the packet is dropped; if not, the packet is duplicated and forwarded to all neighbors.

ii. Reverse Path Forwarding (RPF)

a. If a packet arrived on the link that has a path back to the source; Then the router transmits the packet on all outgoing-links. Otherwise, the router discards the incoming-packet.

b.Such a packet will be dropped. This is because the router has already received a copy of this packet (Figure 5.2).

Fig 5.2: Reverse path forwarding

5.6 Spanning - Tree Broadcast

· This is another approach to providing broadcast. (MST  Minimum Spanning Tree).

· Spanning-tree is a tree that contains each and every node in a graph.

· A spanning-tree whose cost is the minimum of all of the graph's spanning-trees is called a MST.

i. Firstly, the nodes construct a spanning-tree.

ii. The node sends broadcast-packet out on all incident links that belong to the spanning-tree.

iii. The receiving-node forwards the broadcast-packet to all neighbors in the spanning-tree.

Fig 5.3: Broadcast along a spanning-tree

Complex: The main complexity is the creation and maintenance of the spanning-tree.

5.6.1 Center Based Approach

i. A center-node (rendezvous point or a core) is defined.

ii. Then, the nodes send unicast tree-join messages to the center-node.

iii. Finally, a tree-join message is forwarded toward the center until the message either

a. arrives at a node that already belongs to the spanning-tree

b. (or)

c. arrives at the center.

· Figure 5.4 illustrates the construction of a center-based spanning-tree.

Fig 5.4: Center-based construction of a spanning-tree