Pseudorandom thoughts

ISIS : rBridge Nicknames

2011-12-02T04:37:00.001-08:00

Every rBridge in the rBridge campus must have a unique nickname. Incase two campuses are merged resulting in same nicknames for multiple bridges, then it must reconverge to using unique names again.
Nicknames can be configured or selected dynamically.
Nickname value of 0x0000 and those between 0xFFC0 and 0xFFFF are reserved and must not be used for rBridges.
Nicknames are carried in ISIS TLVs along with a priority of use field. The priority is an unsigned 8 bit value where the most significant bit (0x80) indicates that it has been configured. Default value in botton 7 bits is 0x40.
In the case of dynamic nicknames, they can be generated randomly and also reused across reboots. Incase of a collision, the bridge with the higher ISIS ID gets to keep its nickname.
Normally each rBridge has a single nickname. But it may be configured to request multiple nicknames.
Each multi-destination tree has its own nickname.

TRILL : Packet

2011-12-02T02:07:00.001-08:00

TRILL Packet

After TRILL encapsulation, the frame is encoded as a normal Ethernet frame with the DA belonging to the next transit/egress rBridge and SA as the sender MAC address. The Outer VLAN is not mandatory and depends on the port configuration. Incase there are non-TRILL bridges in transit, for them the TRILL packet is completely transparent and they can transparently bridge the frame.

TRILL Header

TRILL Ethertype indicates the type of payload.
V = Version (2 bits)
R = Reserved (2 bits)
M = Multi-destination (1 bit)
OpLng = Length of trill options
Hop = TTL
Nicknames = 16 bit values designating the ingress and egress rBridges.

TRILL overview

2011-12-01T20:47:00.001-08:00

Introduction

TRILL is Transparent Interconnection of a lot of links. It is a IEEE standard for doing routing in layer 2 using a link state protocol such as ISIS. The forwarding unit in a TRILL network is called an RBridge (Routing Bridge) and a collection of RBridges operating in tandem is called an RBridge Campus.

Main benefits of TRILL

Can reduce the spanning tree domain or completely eliminate it in a large L2 environment.
Based on link state routing and supports multi-pathing.
Prevents need for MAC learning in the transit nodes.
Extensible as its based on ISIS.
Gives an option of TTL (hop count) to prevent endless looping

Packet flow

When a native Ethernet (or in future extensible to other L2 technologies) frame either with a 802.1Q VLAN header or without it, enters a TRILL cloud at some ingress rBridge (say RB1), it is encapsulated in a TRILL header and "routed" through the cloud on its way to the egress rBridge (say RB3), provided the egress rBridge for that particular destination MAC address is known.
The routing within the cloud (say at RB5) happens only based on the egress rBridge stored in the TRILL header, this facilitates the option to skip end MAC address learning in the transit rBridges.
Once the packet reaches the egress rBridge, it is decapsulated and the native frame is sent out.
The native frame must be mandatorily added to the payload along with the VLAN tag and it will be either sent along with the tag or without it depending on the properties of the port on which it is egressing.
If the destination MAC address is unknown or if it is a multi-destination (either IP generated multicast packet or any other kind of L2 multicast packet), it is sent via a pre-built distribution trees.
rBridges do not participate in spanning trees but they can be a leaf node in a spanning tree. Hence BPDUs do not get forwarded via TRILL clouds.

Data Center Bridging : Introduction

2011-12-01T20:06:00.001-08:00

In an effort to make Ethernet work with data center storage protocols such as FC and iSCSI, there are a few enhancements done to make Ethernet support traffic management capabilities. These are collectively known as Data Center Ethernet (DCE) or Data Center Bridging (DCB). The important standards within DCB are,

Priority Flow Control (PFC) 802.1Qbb Also known as per-priority PAUSE. This extends the existing PAUSE mechanism in Ethernet to also specify a priority value for which the PAUSE should be implmented. The bridge sends an array of 8 fields containing a 2 octet priority_enable_vector and a 2 octet time_vector field. The priority_enable_vector specifying each of the 8 priorities for which PAUSE should be active and the time_vector field gives the corresponding PAUSE interval. The interval is measured in pause_quanta, which is the time taken to transmit 512 bits on the particular PHY. The range of valid PAUSE intervals are 0-65535.

Enhanced Transmission Selection 802.1Qaz It introduces a new 4 bit Priority Group ID (PGID) field. The PGID values 8-14 are reserved and 15 is a special "No bandwidth limit" option. One or more priorities can be mapped to the values 0-7. Each PGID is allocated a maximum percentage of bandwidth on the particular link and it cannot exceed that value.

Congestion Notification 802.1Qau Link-level pausing can cause the congestion to shift to a secondary location from the primary one. To avoid this congestion control must actually be implemented at the source of the traffic and backward congestion notification mechanisms to inform the source are implemented in this standard. The point where congestion occurs is called Congestion Point (CP) and the one that handles it is called Reaction Point (RP). Congestion level is indicated by the CP to the RP and the RP immediately reacts by stopping the transmission and then gradually increasing it. The increase happens in two phases Fast Recovery and Active Increase.

DCB Exchange protocol 802.1Qaz It is used to exchange information with the immediately connected peers. It does not support multiple neighbors and works only on point to point connections. DCB exchange parameters can be classified as two types, administrative, pertaining to configuration and operational, pertaining to real time statistics. They are packaged into organization specific TLVs transmitted via the LLDP protocol. Currently there are TLVs for priority groups, PFC etc.

ISIS C5.5 : P2P over LAN

2011-11-28T19:34:00.001-08:00

It is common to have topologies where the physical connect media is a broadcast media such as Ethernet but there are only two routers connected to the media as in a point to point circuit. In such cases, to treat such connections as a p2p connection reduces a number of overhead in routing protocols such as OSPF and ISIS. For example, in ISIS, it would not be necessary to run DIS election on this link. Also it would not be necessary to generate a separate prefix TLV and the adjacency itself is enough to use this link properly in the SPF calculation.

To facilitate such operation, the rules are defined in RFC 5309 to configure a link as a p2p link irrespective of the characteristics of the physical media. However since this is configuration based, there must be mechanisms to check whether the connection is really configured correctly. For example, if a LAN Hello message is received on such a p2p forced link, then the adjacency must not come up because the notion of the link is different on both sides and vice versa.

It is still required that the links have IP address and they go through the normal ARP process for resolving the next-hop etc. as they do in LAN circuits. To replace these with operation similar to p2p circuits would be under a different scope.

ISIS C5.4 : Fragments exceeding 255

2011-11-28T18:23:00.001-08:00

Due to some additions to the TLV structure like subTLVs and features like traffic engineering, it may be possible that the LSP becomes very big that after fragmentation it may exceed the max fragments of 255. There are couple of ways to solve this problem as detailed in RFC 3786. The first mode is to be used in cases where there are some routers which do support this new operation and we need to be backward compatible. However the first model has a few drawbacks and there is a second mode or operation which can be run if all routers support the mode.

Operation Mode 1

In this mode, the information that doesnt fit into the first 255 fragments in the physical router S is sent as if it is originating from a different virtual router S'. S' is only connected to the physical router through a p2p link and is a leaf, the cost of the link to S will be zero. Any connectivity loss to S will automatically result in loss of connectivity to all virtual routers it is connected to. The only adjacency that will be advertised by S' is the one to S with a cost of maxMetric-1 (this is to satisfy the bidirectionality check). Incase there is more information, then more virtual routers can be added as per the requirement.

This model is very elegant in the sense that other routers need not be aware of this scheme at all and can use the normal SPF mechanisms to compute the routes. However the restriction is that only leaf information can be advertised using virtual routers

Operation Mode 2

In this mode, any information can be advertised using the virtual routers. The SPF algorithm will be run after the router consolidates the information from the physical router as well as the associated virtual routers.

TLV #24 (IS Alias ID TLV)

This TLV is used to advertise the physical router information (S) so that the receiving routers can advertise the virtual router LSPs with the actual physical router LSP. This TLV is used in both modes.

ISIS C5.3 : Multi-Topology

2011-11-28T03:43:00.001-08:00

ISIS has support built in for handling different topologies at the same time and distributing and computing routes for the different topologies separately. There are a few well-defined topologies defined in the RFC itself, namely:

IPv4 Unicast (0)

In-Band Management (1)

IPv6 Unicast (2)

Multicast (3)

IETF consensus (4 - 3995)

Experimental (3996-4095)

Topology ID information needs to be added to the TLVs so that the information pertaining to the different topologies can be distinguished. The IIH carries the different topologies supported by the router in TLV #229 defined for the purpose. It has a vector array of 12-bit topology ID information.

Multi-topology supporting LSP TLVs are also defined. For IPv6, there is a Multitopology IPv6 reachability TLV #237 and a Multitopology IPv4 TLV #235 is defined for IPv4 topologies.

For IPv4 with default topology #0, either TLV 235 can be used or the original TLV #135 can be used.

ISIS C5.2 : Interaction with BFD

2011-11-28T01:41:00.001-08:00

Normally an ISIS neighbor adjacency for IP routing can come up independent of the BFD state on the link. However for ISIS there is a unique problem. Sending and receiving IIH packets does not happen at the IPv4/IPv6 level. And BFD is a protocol that maintains connectivity information at the IPv4/IPv6 level. Hence it is possible that between two routers IIH connectivity still works and adjacency is up but the link is not capable of handling any IP data traffic. This has been fixed using RFC 6213.

To avoid the above scenario a new TLV #148 has been defined to carry the BFD capability on each link to be included in the IIH packets. This TLV indicates if an interface has BFD capability. If both sides of a link have BFD capability, then the ISIS adjacency should come up only after the BFD session between the two is up. Similarly if the BFD session goes down, then the adjacency is expected to go down immediately irrespective of whether IIHs can still be exchanged.

In the case of LAN circuits, the rules apply for adjacencies between two routers which have BFD enabled on the LAN interface. If the BFD is down, then the routers are excluded from the adjacent routers advertised by the pseudonode.

ISIS C5.1 : Mesh Groups

2011-11-28T01:24:00.001-08:00

In ATM and FR scenarios, in many networks routers are connected as a mesh using multiple logical point to point links. In these cases, ISIS LSP flooding can result in an enormous amount of redundant information. For example in the below topology.

When a new LSP is flooded by System 1, it is received by System 3 directly. It is also received by System 2 and flooded back again to System 3 and so is the case with System 4 flooding it to System 3. It is not apparent to these routers that System 3 is directly connected to System 1 and does not need to know about System 1 generated LSPs.

To overcome the above problem RFC 2973 defined Mesh Groups. A mesh group is defined as a set of point to point circuits that provide full connectivity to a set of Intermediate Systems. Each circuit now has two attributes :

meshGroupEnable : meshInactive, meshBlocked and meshSet

meshGroupNum : Integer specifying the mesh group

The working is fairly obvious, if a new version of the LSP is received, it is not flooded back into circuits which have meshSet and which have the same integer specifying the mesh number. The routers assume that the originating router would have done the update by itself as its a full mesh.

The main disadvantage of this method is that it is purely driven by configuration and the configurations are also static.

ISIS C4: Leaking L2 routes into L1

2011-11-27T22:31:00.001-08:00

In ISIS, a L1 area is like a stub area of OSPF. It has full information about the networks that are within the L1 area but it uses the nearest L2 router to get to the networks that are outside its area. It is natural that there are multiple L2 routers that are connected to a L1 area. In that case there will be some networks external to the L1 area that are reachable shorter via one L2 router ad some networks which are shorter via the other L2 router. However this information is not normally available to the routers in the L1 area because L2 routes are not normally leaked into the L1 area.
In cases where the above problem is significant, it is possible to intentionally leak L2 routes into L1 area so that a proper routing decision can be made. However care must be taken to ensure that only the necessary routes are leaked as otherwise it can be overwhelming for the L1 router.
The route computation for the L2 leaked routes is a simple selection based on cost between the prefixes advertised by the different L2 routers.
Care should be taken not to re-advertise the L2 leaked routes back into L2 by L1 routers as this could cause routing loops. For this there is a need to distinguish which routes are the ones leaked. This is done by adding an Up/Down Bit in the Old Style TLVs #128 and TLV #130. This occupies the MSB of the default metric field. If the bit is set to 1, then it is a leaked route. In the new style TLV #135, the support for the bit was present from before and is used for the purpose.

ISIS C4: SPF

2011-11-27T21:35:00.001-08:00

SPF computation

SPF run is based on Djikstra's algorithm.
The high level working of the algorithm is as follows.

Initially all nodes are put into an UNKNOWN list.
The router that performs the computation moves itself into the PATH list.
Add all the nodes that are connected to the source router into the TENT list along with the cost to reach them.
Now scan the TENT list and find the node with the least cost and add it to the PATH list. Before adding the node into the PATH list verify that there is bi-directional connectivity to the node, ie. the node also has advertised a path back to the source node.
Now add all the nodes that are connected to the node that got added to the PATH list in the TENT list.
Again choose the TENT node that has the least cost from the source and move it to PATH list and repeat the above process.
If there are more than one node in TENT list with the same cost, then choose one randomly to be moved into the PATH.

SPF computation takes place in two stages:

The first stage mentioned in the steps above needs to only know the information that is advertised in the IS-Reach TLV, ie. we need to know only the adjacency information and the cost of the paths.
The second stage involves listing all the network prefixes that are hanging off the nodes and assigning a first hop to reach them. In this stage the IP Reachability TLVs are used.

There are three different kinds of SPF:

Full SPF This is what has been described above and consists of two passes to build the entire routing database for the protocol.
Partial SPF This is useful when we know that only the prefix information has changed, ie. either the prefixes now have a different metric or they have been added or deleted. In such a case, we know from the above sequence of steps that only the second stage needs to run and the first stage data is completely unaffected.

Incrementatl SPF This is useful in a couple of scenarios. For example, a adjacency has gone down but we know from our earlier SPF run that the adjacency that went down was not being used in the actual shortest path, then this change can be completely ignored. However we should understand that this change maybe irrelevant to only this router and this path may be used by some other router in its shortest paths tree. Hence this decision is purely local to each router. the second instance is when a router itself is a leaf, then if there are any changes in the metrics of the adjacency that router has with its attachment point can be safely ignored by all routers because they are not going to have any impact on the calculated paths.

ISIS C3: Fragmentation

2011-11-22T02:24:00.001-08:00

ISIS performs fragmentation at the application level. The minimum MTU that is supported by ISIS is 1492 bytes. To make sure that a particular link supports this minimum MTU, the IIH (Hello) message is explicitly made to be of a size bigger than that by adding padding TLVs. It is also required to add multiple padding TLVs because the maximum size of one padding TLV is only 255 bytes. Once the minimum MTU is working, the adjacency comes up.

When LSPs are to be exchanged across the link, it is safe to assume that the minimum MTU is atleast supported. So when a LSP needs to be generated that is bigger than the minimum MTU, it needs to be fragmented at the LSP level. A LSP ID is thus designated as,

System ID - Pseudonode ID - Fragment ID

A system thus generates multiple unique LSPs for the database information with just the last byte differing. ISIS does not necessarily have to wait for all the LSPs to arrive before it can begin the SPF computation. This is because the individual TLVs within the fragments are all self-contained. For example, if we need to send a IP Reachability TLV for a huge number of internal routes, then they will be split into multiple IP Reachability TLVs such that one whole TLV fits into one LSP packet.

For CSNP and PSNP packets, the individual units within each of them are the TLV #9 specifying the LSP-IDs that are either being advertised or requested. Since there is no relation between the different LSP-IDs that are being advertised, they can be conveniently split into multiple packets and sent as multiple different Type #9 TLVs.

ISIS C3: Sequence number packets

2011-11-22T02:17:00.001-08:00

Sequence number packets are used to ensure that all the routers in the network have the latest information regarding the LSPs. There are two types of sequence number packets.

Partial Sequence Number Packet (PSNP) : Used for requesting or acknowledging specific LSP-IDs from a neighbor.

Complete Sequence Number Packet (CSNP) : Used for advertising the latest sequence number and age for all the LSPs that are present in a router's database.

LSP Entry TLV #9 is used for this purpose.

The TLV can contain information about multiple LSP-IDs that are present in the database.

ISIS C3: New style TLVs - Wide metrics

2011-11-21T22:01:00.001-08:00

Limitations of the old IP extensions for IPv4 are

Limited space for specifying metrics (6 bits)
Fixed nature of the TLV without any option for extending it to add new information as protocol develops.

IETF enhanced the existing IS-reach TLV #2 and IP Reachability TLV #128 with the above goals in mind to create two new TLVs in RFC 3784

Extended IS reachability TLV #22

The subTLVs may be used to advertise the IP address of the neighbors.

Extended IP reachability TLV #135

The metric field is 32 bits wide and can be used to reverse encode the interface bandwidth (ie. higher bandwidth link gets a lower metric and vice-versa). The subTLV bit field denotes whether there are optional subTLVs following the base TLV. The subTLVs can be used to extend the functionality in future by adding new formats.

The prefix has been made variable length so that only the useful bits can be encoded in it. The decoder knows how many bytes are available in prefix using the prefix length field. The metrics no longer can specify the I/E bit (internal-external). All prefix information is advertised in a consolidated manner using TLV #135.

Most implementations today support both the old style and the new style metrics. The new style is also referred to as wide-metrics because the metric width has been increased to 24 bits in TLV #135 and 24 bits in TLV #22.

ISIS C3: IPv4 Extensions - Old Style TLVs

2011-11-21T21:44:00.001-08:00

ISIS has been extended by RFC 1195 to support IPv4 routing support. The LSPs that are used for conveying IP information are as follows:

Internal IP Reachability TLV #128 This is used for conveying the information of networks that are directly connected to the router. It is possible that we may need to advertise networks belonging to interfaces that are not enabled for ISIS. This is accomplished by configuring them as passive interfaces. Each entry is 12 bytes wide and a number of networks can be packed into a single TLV upto the maximum size possible. Since the TLV length is a one-byte field, only sizes upto 255 can be specified. Hence we can pack upto a maximum of 21 networks in one TLV.

Protocols Supported TLV #129 This is used for conveying the protocols that are supported by the ISIS instance either at the interface level or at a router level. This TLV enables ISIS to become truly protocol independent. The codes used for IPv4 are 0xCC and for IPv6 are 0x8E. If the neighboring router doesnt advertise the protocol support for IPv4, then a IPv4 adjacency does not come up.

External IP reachability TLV #130 and Inter-domain information type TLV # 131 These are used for propagating external domain route information into ISIS. The TLV #130 is similar to TLV #128 to advertise external domain IP networks and TLV #131 gives more information about the domain like AS number etc. These are no longer used.

Interface address TLV #132 This is used for conveying the configured interface addresses to the neighboring router. If a neighbor finds its own addresses configured on the other router, adjacency does not come up.

ISIS C3: IS-Reach TLV

2011-11-20T02:05:00.000-08:00

To build a graph that can be used to compute the Shortest Path tree to the different parts of the network, there needs to be two inputs. One gives the adjacencies between the routers in the network along with the metrics for traversing that adjacency and the next is the networks that are hanging off each of the routers. The first information is distributed across the network by the use of the IS-Reach TLV #2.

The Neighbor ID is a combination of 6 bytes of System ID and 1 byte for Pseudonode ID. There are different types of metric that can be advertised incase it is required to compute different paths depending on different metrics.

Spanning tree Root Guard and BPDU Guard

2011-11-17T17:50:00.001-08:00

Root Guard

Administrators have some control over which bridge can become the root port. This is by modifying the bridge priority and the bridge that must definitely become the root can be designated a priority of 0. However it is possible that there may be some other bridge with priority 0 with a smaller MAC and STP will elect that as a root bridge. Refer to this link for an example of how a rogue bridge can cause a non-optimal topology to be built up.

Root guard feature ensures that when a superior BPDU arrives on a port that is enabled for this feature, the port is set into a STP-inconsistent listening state. The port never moves to a root port state. This makes sure that the BPDU sender never has a chance to become the designated port on this link. When the superior BPDU ceases to appear, the port is automatically transitioned to designated port state.

BPDU Guard

When edge ports are connected to servers, it is possible that a rogue server sends out a BPDU on the edge port causing confusion in the STP calculations. So when it is given that a port will definitely be an edge port, BPDU guard can be enabled to protect such malicious BPDU messages from the servers. When such a port receives a BPDU, it automatically disables the port and manual intervention is required to bring it back up. BPDU guard is usually configured in conjunction with portfast feature on the edge ports.

Rapid Spanning Tree Protocol

2011-11-14T23:08:00.001-08:00

The most important issue with the original spanning tree algorithm is the fact that the transition from a blocked state to a forwarding state takes 50secs with the default configuration parameters and during this time, it is possible that a lot of traffic is blackholed during this period. To alleviate this concern and many other minor issues with original STP, Rapid Spanning Tree Protocol (RSTP) was standardized as 802.1w. It was subsequently integrated into the original 802.1d STP IEEE document and today the default spanning tree implementation is RSTP. Devices can fall back to original STP mode incase they see STP BPDUs.

The major differences between RSTP and STP are:

RSTP defines port roles in addition to port states. Two new port roles defined are alternate and backup. Alternate port is the second best path to reach the root bridge and is computed along with the root port. If for some reason the root port goes down, the alternate port is immediately moved from blocked to forwarding state without any intermediate states. When a bridge connects using more than one port to the same LAN segment, the second best port other than the designated port will be marked as the backup port. If the designated port goes down, then the backup port will be transitioned to forwarding state.
RSTP has done away with the timer based listening and learning states for moving a port to forward on point to point connections. Instead it has introduced a proposal and agreement based mechanism, where two bridges on a dedicated link can quickly converge on who will be designated port for the LAN.
BPDU timeout is no longer 10 * hello time, it has been reduced to 3 * Hello time.
BPDUs are no longer generated only by the root, every bridge generates a BPDU in the generation interval.
Topology Change Notifications are flooded directly by the bridges across the network and they no longer need to propagate to the root and get sent in the next BPDU message. Also the forwarding table entries are immediately cleared on receiving the TCN.

Here is a link for a tabular listing of the differences.

Spanning tree Topology Change

2011-11-14T22:41:00.001-08:00

Topology Change Notification

There is a need to propagate any topology change due to spanning tree activity across the network. The reason for this is that forwarding entries may have to re-learnt after the topology change.
For example, assume a bridge B1 was forwarding packets to another bridge B2 and some port of B1 has become blocking now because of spanning tree protocol making it lose connectivity to a few end-station MACs. There would already be forwarding table entries in B2 pointing to B1 for those MACs even though there will be a new way to reach the MACs that were once behind B1. Till we receive any packet from those sources in the new path, we will be blackholing the traffic by sending them to B1 where they could get discarded. Hence even though B2 is not involved in the spanning tree topology change that happens at B1, it is still necessary to flush out the forwarding table entries.
When a port that was forwarding changed to blocking or a port that was blocking changed to forwarding the bridge on which the event happens generates a new message known as Topology Change Notification (TCN) and sends it on the root port. The bridge along the path to the root, then acknowledges the packet using a Topology Change Acknowledgement (TCA) and forwards the TCN towards the root. When the root bridge receives the TCN, it will set the Topology Change Flag in the next BPDU message that it is generating. Whenever a bridge receives a BPDU with the TCN flag, it sets the flag in its next outgoing BPDU as well.
There is a short station cache timeout (default=forward delay=15secs) that is started on receiving a BPDU with the TCN flag set and on expiry of it, the forwarding table entries are flushed.

Problems

One obivous problem with the TCNs occurs when we have end stations connected to the network flapping. In this case the port connected to the end station moves from forwarding to blocking back to forwarding. This warrants generation of a TCN and subsequent flushing of all MAC address entries across the network. To alleviate this problem, we can use Cisco's portfast feature. If a port is configured for this feature, then it is assumed that it only connects to end stations and whenever there is a spanning tree state change in the port, no TCNs are generated.

Spanning tree states

2011-11-14T21:04:00.001-08:00

There are basically 5 states in the original spanning tree algorithm.

Disabled
Blocking
Listening
Learning
Forwarding

Let us look at when the state transitions happen.

Initially a port is in disabled state and needs to be enabled by the administrator.
Once it is enabled, it is immediately put it into Listening state. Packets are not forwarded in Listening state and no MAC learning happens. If this bridge is turned on new, the bridge assumes that it is the root and starts transmitting BPDUs to that effect until it hears something better from its neighbors. If it hears a better BPDU from a neighbor, it immediately transitions the port to blocking state.
Once the listening state is completed for a predetermined amount of time, if at the end of the time, it still has not received any better BPDU on the interface, then it moves to learning state. Packet forwarding still does not happen but MAC learning happens. This is to pre-build a MAC database before actually forwarding starts to happen. In this state if it receives a better BPDU, it can still transition to blocking state.
Once learning state is completed, the port moves to forwarding state. It can either be the root port or designated port from the protocol point of view but there is no difference in the forwarding paradigm and the port is kept up for both forwarding incoming and outgoing packets and also for MAC learning.

The amount of time that is spent in the learning and listening states depends on a parameter known as forward delay. This is the amount of time that it takes to propagate BPDU from one end of the network to the other and the default is 15secs. The purpose of the listening/learning states is to allow propagation of the BPDUs from one of the network to the other and back to be fully sure that all the bridges in the network have consistent information to create a loop-free tree.

In a steady state, the root bridge transmits the BPDUs every 2 seconds. On reception of this BPDU, the other bridges generate and forward their own BPDU on all their ports. Ports in all spanning tree states except disabled receive and process BPDUs.

The max age for the BPDU originating from the root bridge is by default 20secs. So if a interface breaks down at any part of the spanning tree, bridges with other interfaces on LAN, the will stop receiving the better BPDU from the bridge and will timeout the existing best BPDU at the end of 20 secs. At this point, the designated port election will need to again happen on the LAN. For this all the ports on the LAN will be moved to listening state and a new bridge with the least cost to the root will be selected. The other ports move to blocking state. For the port that is now transitioning as a designated port on the LAN, it will hence take (20+15+15=50secs) for the transition to complete to forwarding state. All traffic coming into the LAN will be blackholed during this period and this is one of the items that will be addressed in the newer Rapid Spanning Tree Protocol (RSTP) that we will discuss later.

Spanning tree algorithm basics

2011-11-14T20:37:00.001-08:00

Elect a bridge among all the bridges of all LANs as a root bridge.
Select the port that has the shortest distance from each bridge to the root bridge. This is called the root port.
For each LAN choose the bridge that has the shortest distance to the bridge. This is called the designated bridge for the LAN and the port on the bridge that connects to the LAN is called the designated port.
All ports that are either root ports or designated ports are in forwarded state and all other ports are in discarding state.

From the above it must be clear that the working of the protocol has to be broadly based on these concepts.

Every bridge must have a ID which is unique across the domain. Root bridge election can be done based on this root bridge ID.
Information packets must be sent along all LAN segments of the network containing the bridge's own bridge ID and the best root port ID that the bridge is aware of and the cost to reach that root bridge from this bridge.
With the above information, it is possible at some point for all bridges to converge on the best root bridge for the entire network and their own cost to the root bridge.
It is also possible to know which port on the bridge is the one that has the lowest cost to the root bridge. This port is designated as the root bridge. In the cases where there are more than one port having the same cost, then the interface ID is used to select the root port.
On a LAN, all the connected bridges know the bridge that has the best cost to the root. This bridge becomes the desginated bridge and the port on the LAN of that bridge becomes the designated port. All other bridges block their ports that are connected to the LAN because they are not having the most optimal path to the root to forward the traffic.

The above 5 steps are necessary sufficient to complete a spanning tree algorithm convergence. To add a little more depth of information to above,

Bridge ID A bridge ID is formed by concatenating 2 bytes of priority along with a unique MAC address on the bridge. The lower the root ID, it is more preferred. The priority is prepended to the MAC, so by assigning a lower priority, we can influence the root bridge selection.
Information exchange between bridges is done using a Bridge Protocol Data Unit (BPDU) packet. It is a L2 packet sent with a SAP value of 01000010 and multicast to special MAC address. A BPDU contains among other things.

Root Bridge ID
Cost to Root Bridge
Transmitter Bridge ID
Age for which the message is valid
Configuration parameters

A received BDPU is better than the BPDU than what we are generating on a particular LAN segment, if the number generated by a combination of Priority.Root Bridge ID.Cost.Transmitter bridge ID is lower than what we generated on the interface. In that case, we accept that the other bridge is a better choice for transmitting packets on the LAN and start to block our port on that LAN.
Select one among all the best BPDUs on each port of the LANs we are connected to and that port becomes the root port for the bridge.

Bridges and need for spanning tree

2011-11-14T20:07:00.001-08:00

Transparent Bridge is transparent because it doesn modify anything in the packets that pass through it at any level, L2 or L3.

Learning bridges learn the source MAC of a packet on the incoming interface. In future any packet that has this MAC as the destination MAC will be forwarded only on that interface. When the same MAC is seen as source MAC in another interface, the original entry is re-learnt using the new interface. Otherwise MAC addresses are usually timed out when there is no traffic from the source for a particular period of time. Unknown MACs are replicated and flooded on all ports of the bridge or the VLAN.

Qualified learning implies learning a MAC address along with a VLAN. This is important when non-unique MAC addresses can be present in a multi-customer environment. Today almost all hardware L2 forwarding tables support qualified learning.

Problem of loops

When packets are replicated and flooded, multiple copies of the packet start to exist on the network.
There is no TTL like mechanism for discarding a L2 packet once it has reached the particular number of hop traversals.

In the above when A transmits a packet to a host on LAN2 which is unknown, the packet is forwarded on to the LAN2 segment by all 3 bridges. They also each learn that A is on LAN1.
When the packet that is forwarded by B1 reaches B2, B2 now incorrectly changes its source learning such that A now resides on LAN2. Similar is the case when B1 receives the packet that is transmitted by B2 or B3.
Since the packet is still coming in for an unknown MAC, B2 again retransmits the packet that B1 sent on LAN2, onto LAN1 again. Similar is the case with B1 on the packet it received from B2. Now the packet again reaches the bridges and A is learnt on LAN1. This cycle continues to happen and the packets keep getting replicated and flooded on all segments again and again till the entire network is completely consumed by infinite copies of the same packet.

Spanning tree algorithm attempts to solve the problem by having a tree rooted at one particular bridge and providing loop-free connectivity to all the LAN segments connected in the network.

802.1ah Provider Backbone Bridging

2011-11-09T00:18:00.000-08:00

802.1ad doesn’t offer a true separation of customer and service provider L2 domains because the MAC addresses in the packets are still the customer generated MACs. To overcome this restriction, concept known as Provide Backbone Bridging or Mac-In-Mac was introduced. In addition to adding a new MAC encapsulation, it also provided a way to add a service instance so that flows can be tagged in L2 and there can be some applications in future like E-VPN that can make use of it.

B-DA : Backbone destination MAC
B-SA : Backbone source MAC
B-VID : Backbone VLAN ID
I-SID : Service Identifier (24 bits)
S-VID : Service Provider VLAN ID (part of 802.1ad)
C-VID : Customer VLAN ID (part of 802.1q)

Service Encapsulation also contains priority, Drop Eligibility Indicator (DEI) and No Customer Address (NCA, for OAM frames) flags in addition to I-SID

Ethertypes are as follows:

Outer header : 0x88A8 (Note that outer header is of a similar format as a 802.1q frame, so there is no change in hardware as far as the bridges in the Provider backbone are considered)
Service Encapsulation : 0x88E7
Customer frame S-TAG : 0x8100
Customer frame C-TAG : Payload type (eg: 0x0800 for IP)

802.1q and 802.1ad

2011-11-08T22:39:00.000-08:00

802.1q defines the system of VLAN tagging for a packet. It should be noted that it is VLAN tagging and not VLAN encapsulation because the actual packet is modified with the addition of VLAN information and it is not encapsulated with a different header. The original L2 header fields such as destination MAC and source MAC will continue to be in their original positions, following which a new 32 bit 802.1q header is added which contains the following information.

16 bits TPID (Set to 0x8100, this is present in the traditional Ethertype location with the packet and identifies that the packet contains a 802.1q header)

3 bits PCP (Priority Code Point) 3-bit priority field for Ethernet as defined by 802.1p

1 bit CFI (Canonical Format Indicator) If 1, indicates that the MAC address is in non-canonical format

12 bits VID (VLAN ID, max can be 4095, since 0x0000 and 0xFFFF are reserved max usable is 4094)

When 802.1 SNAP encapsulation is used with OUI of 00-00-0 and protocol ID field in the SNAP header containing the EtherType, then the protocol field will be set to 0x8100 and the 32 bit 802.1q header will be appended after the SNAP header.

When double tag encapsulation based on 802.1ad is used the EtherType of the first tag is specified as 0x88a8. This implies that there is another tag following the first one and the second tag will continue to have EtherType of 0x8100. The outer tag is usually the provider VLAN and known as S-TAG, the inner tag is the customer VLAN ID and is known as C-TAG.

It should be noted here that 802.1ad does not solve the problem of customer MAC learning as the original MAC header of the packet still contains the customer source and destination MACs. It only provides a way to hide the customer VLAN in scenarios where there is a requirement for more than 4K VLANs or where there is a need for hiding the customer VLANs from the core L2 network because they are non-unique. This mechanism is also known as Q-in-Q. For solution to prevent customer MAC from being learnt we will need support for Provider Backbone switches which we will come to later.

Data Center Networking Challenges

2011-11-08T00:40:00.000-08:00

Explosion of MACs, IP addresses and ARPs

This is the first and foremost technical challenge for a data center with highly virtualized servers. If a typical rack can contain about 15-20 physical servers and each physical server has about 40 virtual machines within it, then per rack we will have 800 MAC and IP addresses to deal with. This number is expected to go up significantly in the coming months as servers become more and more capable and can support maybe even up to 100 virtual machines.
The issue with more MACs per rack will affect a ToR switch in the sense that it has to learn the MACs in its Forwarding Database (FDB). But the problem will be more pronounced in the aggregation switches that cater to multiple racks. With future scales of operation, the aggregation boxes may have to deal with maybe a million MACs in a medium sized data center. Adding support for more MACs in the FDB increases the cost of the forwarding hardware.
Another important problem with this scale of IP addresses is the need for doing ARP resolution using traditional means which is broadcast. Usually DCs will be segmented into VLANs to ensure logical separation of servers, however the scale of a single VLAN may be reasonably big to cause flooding of ARP packets for thousands of hosts. This not only affects the link capacity but also affects the processing power of the servers/hypervisors as in traditional IPv4 ARP, every node has to process the ARP request before choosing to drop it. In IPv6 though there is an alternate for this by means of using solicited multicast node address so that atleast the processing part is handled. However it is difficult to come up with such a scheme for IPv4 because the implementations on the servers need to change for this.
In addition to ARP processing being a problem for the servers, it is a bigger problem for the routers involved in the L3 forwarding at the aggregation/core level because they are now expected to handle all the ARPs for all the MACs in the L2 administrative domain which could run up in millions.

Restricted VLAN space

If traditional VLANs are used then the number of separations possible in a data center L2 network will be only 4K VLANs. It is also possible that not all 4Ks can be used for actual VMs. When considering a multi-tenant DC supporting a huge number of customers, this restriction is very limiting as a single DC may be serving thousands of different customers wanting separation of data flow.

Multi-path support and optimal routing

Traditional spanning tree algorithm implementation blocks out redundant ports and does not utilize their bandwidth. Earlier this was not an issue because the traffic from the servers to the ToRs was not really populating the links fully, however with the introduction of VMs and more powerful servers with 10G NICs, it is easy to fill the pipe and also push such traffic into the aggregation/core layers. This means unutilized bandwidth is no longer acceptable.
One solution for the above problem is to use the concept of M-LAGs or multi-chassis trunking or SMLT. However this cannot be extended to provide any path based routing as it is a very local concept between the set of switches.

Optimal traffic forwarding

It is also expected that most data centers have requirements about the time taken to reach from one VM to another within the same DC and fast response time for packets to be sent out of the DC. In a large data center with multiple L2 aggregation switches, it is natural to have multiple hops before the packet actually reaches the destination ToR for inter-DC communication. Each hop in the path introduces a latency and it is also not guaranteed that this path will be the most optimal one to reach the destination ToR.
To address the above problems, TRILL and Shortest Path Briding (SPB) are used both of which are based on IS-IS and try to find the optimal path as well as support ECMP so that solutions like M-LAG are not needed.

vMotion and VM relocation

Through vMotion a VM can be relocated on to another physical server that may either be in the same DC or in a different DC in a different geographic location. There are some needs for this including disaster recovery, appropriate load balancing among the servers, server maintenance, DC operation maintenance like need to reduce cooling etc.
When a VM moves to another physical server, it carries its IP address and MAC along with it. In a intra-L3 move, the MAC address alone needs to be updated to point to the new VM across the complete topology. Even this can be an issue because of the need for updation in a huge number of routers. An alternate for this is to have a PBB scheme that is pushed right up to the ToRs so that what is learnt across the aggregation and core routers is only the provider MAC and not the end user MAC.
When VM moves across a DC to another L3 domain, then it is required for tunnelling the data from the original subnet to the new subnet of the VM. But in the long run, it must converge to using a proper shortest path route to reach the destination rather using the triangulation method.

IaaS vs PaaS vs SaaS

2011-11-07T18:51:00.001-08:00

http://www.networkworld.com/news/2011/102511-tech-argument-iaas-paas-saas-252357.html

IPv6 address

2011-10-27T23:37:00.000-07:00

IPv6 has no reserved broadcast or network reserved address within a subnet. Hence all addresses within a subnet are usable for hosts. VLSM is usually not required in IPv6 networks because of the availability of huge number of addresses.

Unicast address

Unspecified or loopback (::/128 or ::1 /128)
Link Local (FE80:: /10)
IPv4 compatible (0:0:0:0:0:0::/96)

Multicast address

Assigned (FF00:: /8)
FF0x:112 bit group ID where x = 2 (Site local) 1 (Interface local) 4 (Global)
Solicited Node (FF02::1:FF00:0000 /104)

Anycast address

Link-local (FE80:: /10)
Aggregatable Global (2001::/16, 2002::/16, 3FFE::/16)
Site Local (FEC0:: /10)

Link local address can be generated by concatenating the 64 bit EUI with the link local prefix.

[FE80::] [54 bits zero] [64 bits EUI]

Site local address can be generated by concatenating 64 bit EUI with subnet mask and site local prefix.

[FEC0::] [64 bits EUI]

Solicited node multicast address

All unicast and anycast IP have their corresponding solicited node multicast address automatically assigned. A device must listen to the solicited node multicast addresses of its correpsonding unicast/anycast addresses without any additional configuration. The address is formed by concatenating FF02::1:FF00:0000/104 with the last 24 bits of the unicast/anycast address.

IPv4 over Ethernet has a protocol field of 0x0800.

IPv6 over Ethernet has a protocol field of 0x86DD.

Multicast MAC mapping

33:33:Last 32 bits of IPv6 address

EUI format

00:50:3E:E4:4C:00 -> 00:50:3E:FF:FE:E4:4C:00

After above step, in the first byte set 0x000000X0 X bit to 1 or 0 depending on whether its a globally unique address or not.

IPv6 Header

2011-10-27T22:51:00.000-07:00

IPv6 header is a fixed size one of 40 octets.
Next Header indicates the header following the base IPv6 header and contains the options.
Flow label is introduced new to assign a tag to a flow. It is not widely used as of now.
Hop limit is similar in functionality to IPv4 TTL field.
Different types of optional header include:

Hop-by-hop options header : IPv4 max packet length is 65535, this is because the length field is 16 bits. In IPv6 there is a hop-by-hop options header that allows specifying a length that is 32 bits wide, so the maximum size supported can be 2^32-1. Such packets greater than 65535 bytes are known as IPv6 jumbograms.
Destination options header : contains information that is specifically to be interpreted by the destination such as Mobile IPv6.
Routing header : Forces a packet to pass through specific routers along the way to the destination.
Fragment header : Used when a node has to send a packet greater than the max MTU on the path.
Authentication and Encapsulation Security Payload (ESP) Header : Used for IPSec. IPSec support is mandatory for routers/nodes supporting IPv6.

IPv4 supports a minimum MTU of 68 bytes and maximum length of IPv4 header is 60 bytes, hence the minimum fragment length is 8 bytes. IPv4 implementations must be able to support a minimum of 576 bytes long IP datagram after reassembly.
IPv6 supports a minimum MTU of 1280 bytes and the minimum datagram size supported should be 1500 bytes.

IPv6 ICMP usages

2011-10-27T22:40:00.000-07:00

Neighbor discovery protocol (ND)
Router Solicitation and Router Advertisement (Determine information about the LAN such as network prefix, default gateway etc.)
Echo request and reply
PMTUD for determining Path MTU (Note that IPv6 does not support transit fragmentation, the source is expected to send packets that are fragmented to the minimum MTU along the path)
Multicast Listener Discovery (corresponds to IPv4 IGMP)
Node Information Query (NIQ)
Multicast Router Discovery (MRD)
Secure Neighbor Discovery (SEND)
Mobile IPv6

ICMP in IPv4 has been used for a variety of DOS attacks and hence many service providers completely block ICMP packets within a secure network. However this is not possible in IPv6 due to the variety of uses that ICMPv6 has.

ISIS C3: Psuedonode

2011-10-27T22:17:00.000-07:00

If all routers attached to a LAN generate updates for neighbors on the LAN, then it will result in large scale flooding across the network. In a N router LAN adding N+1 router will generate N+1 updates to other N routers in the LAN and outside. To avoid this scaling issue pseudonodes are used.
One router is elected as the Designated Intermediate System (DIS) router and it generates the adjacencies for a particular LAN. Hence a mesh will now be changed into a star topology. This DIS router is known as pseudonode because it is a virtual node representing the VLAN.
Pseudonode ID is derived from the System ID of the DIS router. While the NSEL is 0 for physical routers in the ISIS address, for pseudonodes the value can be any non-zero unique number. Since it can hold upto 255 values, a router can act as a DIS for atleast 255 LANs. Beyond that it may have to limit itself rom getting elected as DIS by reducing its priority.
Pseudonode suppression may be done when only 2 routers are connected to a broadcast network. In this case a p2p hello encapsulated in a ethernet frame is sent and if the other end also has the capability, it will form a p2p adjacency over the broadcast link and this eliminates the need for a PN election. Also Adjacency State attribute (#240) can also be used.
DIS election is performed using priority field in the IIH followed by MAC address of the node. There is no concept of backup DIS. A DIS can be preempted due to a new router coming up on the LAN.

ISIS C3: Link State Packets and Reliable Flooding

2011-10-27T22:09:00.000-07:00

Link State Packets

SPF computation operates on the following premise.

Distributed database : Every router has a full copy of the network topology.
Localized computation : Ever router computes the routes independently and does not propagate it outside.

Link State Packets are used to advertise the information regarding the local database of reachable networks and has the following important fields.

Checksum
Sequence #
Lifetime
LSP-ID
TLVs to advertise reachable network information and adjacent router information.

LSPs are sent with a sequence number to ensure that the latest LSP is identifiable if there are delays in propagation.
LSPs have a lifetime that is advertised along with them, the max being 65535 seconds (18 hours). LSPs not refreshed within the lifetime are purged. Typical LSP lifetimes are 20 mins.
Overload bit This indicates that due to memory constraints a router cannot take any more LSPs. This means that the result of SPF will also not be used because using partial SPF is dangerous. Hence a router advertise this bit will be taken off from SPF calculation of router routers for transit routes. For routes that are directly connected to the router and terminating, the router would still be used for calculation.

Reliable Flooding

We need a way to reliably flood the LSP information across a domain so that all routers have the same information regarding the topology of the network.
Forwarding LSPs on all interfaces where there are adjacencies except for the incoming interface is known as flooding. Flooding happens only if the received LSP sequence # is more than the one that was already flooded. This helps stale LSPs from getting weeded out of the network.
Periodically there is a packet that is transmitted with a brief description of all the LSPs in the router's database. When a neighbor sees this list and comes to know of a LSP that is not in its database or a newer version of a LSP than what it has, then it sends a request message to get the LSP. When this process completes, we can expect all the routers in the domain to have the same topology of the network.
Purging LSP is a forceful way of removing an LSP from a database. This may be useful in cases like DIS re-election. In some cases like LSP lifetime expiry as well, the LSPs are purged as due to time shift some routers may not have expired them

ISIS C2: Hellos and Neighbor formation

2011-10-27T21:49:00.000-07:00

There are 4 combinations of Hello (IIH : IS-IS Hello) in ISIS, at one level to distinguish if its a p2p or broadcast link and another two types for L1 and L2. 10859 combines L1 and L2 hello into one type to save bandwidth.
Generally L1 hellos are sent to 01-80-C2-00-00-14 and L2 hellos are sent to 01-80-C2-00-00-15.

ISIS Packet types:

In OSPF adjacency cannot be formed unless there is a matching hold time or dead time configuration. In ISIS the hold time can be changed at any time. Frequency of hello is calculated based on the configured hold time as hold time / multiplier.
LANs use a 3-way handshake mechanism and p2p uses a two way handshake.
In a 3-way handshake, IS Neighbor TLV #6 is sent which contains the MAC address of the nodes from whom IIH are received. When there are two routers, the handshake completes when each router has advertised the other router's MAC address in their IIH TLV #6. In a 3 router scenario, the handshakes complete when all the routers have advertised the other two routers in their respective TLVs. ISIS adjacency is said to be up at the point the handshakes complete.
IS Neighbor TLV #6 cannot be used to determine if a neighbor adjacency is up on a p2p link because it is not mandatory to have MAC address on the p2p liks. Hence Adjacency State TLV (TLV #240) is introduced which contains three state - Down, Initializing and Up.

ISIS C1: Addressing

2011-10-27T21:27:00.000-07:00

OSI requires only one address per router. It is equivalent to configuring one loopback address and then assigning unnumbered IP to all other interfaces in IP world.
OSI address and NET concepts are interchangeable. NET consists of the following parts:

Area-ID
System ID
NET Selector (NSEL)

NSEL is always 0 for ISIS.
System IDs should be unique for each router in the network (this is similar to router ID). System IDs can be of variable length according ISO 10859. However typically they are 6 bytes.
System IDs are usually generated from router ID which is guaranteed to be unique across the network. The ways to dervie it are

BCD encoding 192.168.2.111 -> 192168002117 -> 1921.6800.2117
Direct Hex 192.168.2.117 -> 00 00 C0 A8 02 75
Direct Hex with prepending topology code 192.168.2.117 -> 01 F4 C0 A8 02 75 (01 F4 is the POP code to make it unique across multiple instances of ISIS or in VPN cases)

Area-ID : This is the unique number of for the area and can be variable size between 1 and 13 bytes. Usually 1, 3 or 5 bytes are used. First byte is called AFI. 49 is the AFI for private addresses.
Example ISIS address: 49.1921.6800.2117.00 (1 byte AFI-6 byte System ID-1 byte NSEL)

IS-IS C1: Protocol Basics

2011-10-27T20:46:00.000-07:00

General

ISIS was defined by IETF as a generic link state algorithm capable of performing routing operation for any protocol running above it. Base specification ISO 10589 contains both generic portion as well as portions specific to CLNP. IETF later defined TLVs which are specific to IP and also clarified many other aspects of the protocol for usage in IP networks.
RFC 1195 - First IP aware IS-IS RFC generated by IETF.
ISIS is different from other routing protocols because it runs directly over Layer-2 of OSI reference model. This means it does not need L3 configuration on the interface to work.

ISIS understands two interface types - P2P and Broadcast. On broadcast networks ISIS packets are always multicast to 0180:C200:0014 or 0180.C200:0015.
On Ethernet links, ISIS always uses 802.3 SAP encapsulation with DSAP and SSAP values as 0xFE.
On p2p links, ISIS uses only PPP as encapsulation protocol. Initially there is a OSICP coming into play like LCP which confirms that both ends can understand the OSI protocols. After that the packets are encapsulaed using a 4-byte PPP header.

In OSPF a router can be part of multiple areas and the demarcation of areas is within the router. A link can only connect between two routers in the same area. In ISIS a router wholly belongs to a particular area at a time. However a link can connect two routers in different areas. So the demarcation of areas is within the link. If a link is designated as a Level-1 link, then adjacencies can come up only if it is connecting routers in the same area. If it is designated as a Level-2 link, then the routers can be in different areas. The only restriction is that in a topology, all Level-2 links must form a contiguous network. This is equivalent to a backbone network in OSPF.

In OSPF, the ABR selectively propagates routes from other areas into the areas it belongs to. In ISIS, the L2 router does not by default do this propagation. Whenever a L2 router is attached to another L2 router that belongs to a different area, it sets an attached-bit in its advertisement and this is propagated to all routers in its area. When a L1-only router has to send packets to a destination outside its own area, it just chooses a L2 router that had advertised the attached-bit and sends the packet to it. This is equivalent to adding a default route to that L2 router.
Though it is mentioned that the ISIS router wholly belongs to a area at a time, it doesnt imply that it cannot wholly belong to multiple areas at the same time. A router can be present in more than one area fully at the same time and this concept is used for area migrations. The ISIS packets have the ability to carry multiple area IDs at the same time and if there is a single matching area between two routers across a L1 link, the adjacency can come up.

ISIS Concepts

2011-10-15T22:23:00.000-07:00

Protocols theory and foundation concepts
Neighbor discovery and adjacency formation
Exchanging topology data and reliable flooding of data across the domain
SPF computation
Problems with the protocol and tweaks to solve them

Mesh Groups
BFD
Multi-topology
Fragments exceeding 255
P2P operation over a LAN

Retrieving data after reboot or restart (Graceful restart)
Protocol Extensions

Traffic Engineering
Hostname Exchange
Security
Advertising router information

BGP attributes and path selection

2011-05-03T04:19:00.000-07:00

BGP Path Attributes are used in the BGP to influence the path selection. The different attributes are,

Weight Cisco proprietory, not propagated in messages and is of local significance

Local preference Determines the preference for a particular router for a particular prefix only within a particular AS, propagated by iBGP within an AS.

Multi-Exit discriminator Suggests the preference of a particular exit point from current AS to an external AS, if the external AS is receiving the same prefix from multiple exit points. This is part of the path selection process and may not be the deciding factor for choosing an exit point by neighboring AS.

Origin This is set to IGP for routes injected via network command, EGP for routes learnt via eBGP and Unknown for routes redistributed into BGP.

AS Path List Contains the list of ASs traversed by this particular route

Next Hop Attribute For EBGP, the next hop attribute is the IP address of the advertising eBGP peer. When the route is propagated into iBGP, the same eBGP nexthop is carried into it.

Community Attribute Provides a way to group destinations to which routing decisions (acceptance, preference and redistribution) can be applied. Community can be either a well-known community (in the range 0xFFFF0000 through 0xFFFFFFFF) with pre-defined meanings or they can be private communities. The common well-known communities are no-export (which means dont export this route to other AS via eBGP), no-advertise (which means dont this route advertise to anyone), local-as (which means send to only those in the same AS) and internet (which means send the prefix to everyone)

BGP route selection process

If the path specifies a next hop that is inaccessible, drop the update.
Prefer the path with the largest weight.
If the weights are the same, prefer the path with the largest local preference.
If the local preferences are the same, prefer the path that was originated by BGP running on this router.
If no route was originated, prefer the route that has the shortest AS_path.
If all paths have the same AS_path length, prefer the path with the lowest origin type (where IGP is lower than EGP, and EGP is lower than incomplete).
If the origin codes are the same, prefer the path with the lowest MED attribute.
If the paths have the same MED, prefer the external path over the internal path.
If the paths are still the same, prefer the path through the closest IGP neighbor.
Prefer the path with the lowest IP address, as specified by the BGP router ID.

For more details on the above attributes please refer here.

eBGP and iBGP

2011-05-02T22:28:00.000-07:00

Need for eBGP and iBGP

BGP sessions between peers belonging to different autonomous systems is known as eBGP. This is by default only between directly connected peers. It is possible to overcome this restriction using eBGP multihop though. Suppose a eBGP router is learning a set of prefixes via the eBGP session with a neighboring AS router, it needs to have some way to distribute this information to the other routes in its own AS. To do this it can redistribute those routes into an IGP. However the disadvantage with this is that if the routes need to go out again from AS to some other AS connected elsewhere, the IGP routes need to redistributed back into BGP at that point. However at this point we would have lost all the BGP information such as AS path, community etc. that were there in the original BGP update received. Hence we need to have a BGP mechanism to transfer the prefixes learnt from eBGP within the AS, this is known as iBGP.

Why iGBP neighbors have to be fully meshed?

iBGP sessions always need to be full meshed. Consider a normal distance vector protocol case such as RIP. It is possible that the routes that are advertised by some router come back to the same router again via a different path (even if split horizon is enabled). The reason the routes dont get populated again is because they are now coming with a higher cost than the one we originally advertised. In BGP, the only cost available in the route update for a prefix is the AS path length and the AS path doesnt change when it travels inside an AS. Hence if we receive back the prefixes we sent originally there is no way to detect it so in iBGP. To overcome this, it was decided that no router will re-advertise what it learnt from a particular iBGP neighbor to other iBGP neighbors. This in turn meant that all iBGP routers have to be in a full mesh.

Prefix synchornization

BGP prefix synchronization with IGP routes is only needed for a specific scenario where the AS is a transit AS and not all routers in the AS are running BGP. Consider the below topology.

In the above R6 is going to advertise the routes it learnt from AS 6501 neighbor R7 into iBGP. R2 learns these routes and assume it installs them in the routing table. Now it can advertise these routes to R1 in AS 6502 and R1 can start sending traffic to these prefixes to R2. In R2 the next hop for these routes will be R6 IP address and it will forward those packets along the way to R3. However if IGP is no synchronized at this point and R3 still does not have the route to the prefix, then it will result in blackhole. R2 can know that all IGPs in the AS have the route to the prefix if its own IGP instance also learns this route. Hence in prefix synchronization, for routes learnt via iBGP, the local IGP routing table is checked to see if the same prefix is available and only then the routes are advertised to other eBGP neighbors.

The prerequisite for the above to work is for all BGP routes to be redistributed into IGP. This is not a very favorable scenario usually because it puts an enormous strain on the IGP computing resources. Hence for transit ASs it is a good idea to run BGP on all the routers in the AS and disable route synchronization.

BGP primer

2011-05-02T05:24:00.000-07:00

Introduction

BGP is an exterior gateway protocol that is suited for exchanging large amount of routing information among peers belonging to same or different domains. BGP is essentially a distance vector protocol but there are things that make it more suited for being an inter-autonomous system protocol. They are,

Stability BGP suppresses the impact of interface or route up/down events on the network as flaps can be catastrophic on a huge network. A BGP speaker can generate updates only every 30 seconds on a external BGP session and only every 5 seconds on a internal BGP session. Route dampening is another feature where unstable routes are penalized and not advertised as frequently. Also BGP sessions need not be reset when policies change.

Scalability BGP with modern routers can scale up to hundreds of peer sessions and many hundred thousand routes. As a distance vector protocol BGP advertises routes to its peers only the paths it uses and any change in path information is an implicit withdrawal of earlier information. BGP requires all routers in a AS to be fully meshed, however this limitation can be overcome by features such as route reflector and confederations. Aggregation of routes is supported and important to keep the size of updates low.

Flexibility BGP offers an extensive amount of flexibility in defining policies. There are basically two kinds of policies - routing and administrative. A routing policy can be defined on the inbound or outbound direction and can control things accepting route updates only from a specific upstream provider or changing the path selection. Administrative policies work at the AS boundaries to control things like how many prefixes can be imported into the AS or what routes can be advertised outside of the AS etc.

Using LDP for PW establishment

2011-05-02T01:06:00.000-07:00

Targetted LDP session establishment

LDP normally sends a hello packet to multicast address 224.0.0.2 and UDP port 646 for discovery of neighbors. However when we need to establish LDP session across multiple routers, it is not possible to send multicast LDP hellos. The discovery in these cases is achieved by sending a unicast UDP packet to port 646 with the pre-configured destination address of the LDP peer. A TCP session is subsequently established to that remote LDP neighbor. For L2VPN cases, the PW peer address is automatically picked up usually for establishment of the targetted LDP session for exchanging VC labels.

LDP Information exchange for PW

Every PW is identified by a PW identifier and can carry traffic of one particular L2 session with a CE router. By L2 session we mean, either untagged traffic, tagged traffic with a particular VLAN ID coming on the port or double tagged traffic with specific VLAN ID combination coming on the port. LDP communicates to the other end the mapping between a inner label and corresponding PW ID, which will then map to a corresponding outgoing disposition for that particular unique L2 session. The disposition may involve a VLAN translation as well at the egress PE.

In normal LDP information exchange, for every prefix that the router wishes to receive with a label, the prefix (known as FEC) is advertised along with the desired label to the neighbors. This is done using a label mapping message that contains a FEC TLV followed by a Generic label TLV. Each FEC TLV can have multiple FEC elements but we support only one usually and the type is Prefix FEC (2). The Generic Label TLV can also hold multiple different types of labels but for our purposes this is just a 32 bit number.

For purposes of information exchange for PW scenario, we have defined two new FEC types - 128 (PWID FEC Element) and 129 (Generalized FEC element). 129 is not used widely. The TLV gives the binding of the local label for the PW endpoint, ie. the label with which it is expecting packets for that particular endpoint. The endpoint could be of three types - untagged port, single tagged port or a dual-tagged port. For the single tagged port case, every VLAN ID - port id combination becomes a separate endpoint and labels have to be generated separately for each. For double tagged case, each double tag and port id combination becomes a separate endpoint. This way customer VLANs need not be unique across the box and need to be unique only on that particular port.

The Interface Parameter TLV in the above message gives information about the attachment circuit interface such as MTU, this can be used to check if the two endpoints are interoperable.

When a particular endpoint (Attachment Circuit) is administratively disabled, the label advertised for the same is withdrawn using a Label Withdrawal LDP message.

Once the label is exchanged, we are ready to send packets with the label to the egress PE for suitable disposition. Generally by default routers to add the VLAN tag to the payload before encapsulating it in MPLS packet and it is possible to turn this off by configuration. This tag is then removed at the egress router if there is no tag necessary for the egress outgoing interface. For untagged scenarios the default VLAN is added as in example below. Also in the below packet capture, there is only one hop from ingress to egress, so there is no outer MPLS label due to PHP.

Layer 2 VPN Primer

2011-05-01T22:56:00.000-07:00

Introduction

A L2VPN service is used for multiplexing and transferring data from multiple individual L2 payload sources from one end to an intended recipient on the other end through a public network. For all practical purposes the customer edge(CE) device on one end of the network sees the CE device at the other end of the cloud as directly connected to it via a L2 link.

The emulated L2 service could be anything of the following:

ATM
Frame relay
PPP/HDLC
Ethernet

When TDM based encapsulations are used on either side, it is also important to emulate the circuit based charachteristics of SONET/SDH. SAToP describes methods for transporting low rate TDM digital signals while CEP describes methods for high rate TDM like SONET/SDH. There are two encapsulations for the packet that is transported as a payload. The inner encapsulation is used by the remote endpoint to identify which psuedowire this traffic belongs to, so that it can be routed to the appropriate outgoing interface. The outer encapsulation masks the inner encapsulation while the packet is being transported across the shared network.

The RFC 3985 describes the requirements in general for setting up a pseudowire and the conditions to be met for how the payload traffic flowing through it should be delivered. RFC 4447 describes the usage of LDP to establish a psuedowire connection between two PE routers and distribution of psuedowire identification information for the inner encapsulation. Until now LDP is the only protocol used for establishment of the control plane and LDP was chosen because it had a good TLV based packet format. For outer level encapsulation, either MPLS could be used which in turn can be again using LDP or RSVP, or any other means to encapsulate a MPLS labelled packet can be used.

LDP IGP synchronization (RFC 5443)

2011-04-30T05:50:00.000-07:00

We will briefly look at the LDP IGP synchronization feature.

What is it?

Assume a IGP converged network where the IGP has already computed the routes and installed in the forwarding database. Assume also that LDP is running among the routers in the domain and LDP is still converging. It is now possible that some packets are sent to a neighbor pointed to by IGP before the LDP session to the neighbor is fully established and we have a label to the destination address in the packet. This could be a problem in cases such as VPN, where the LDP outer label has to be present in the packet end-to-end or packet will be dropped due to lack of route etc. This feature, which can be enabled on a per-interface basis and a per routing protocol basis will ensure that packets are not forwarded on a link until LDP is fully synchronized with atleast one neighbor (or all neighbors – see below) on the link.

How is it done?

When an interface is marked as LDP-IGP synchronized, as long as there is no LDP adjacency on the interface to atleast one IGP neighbor, the interface is advertised within the IGP as having the highest metric/cost. This prevents the link from getting used in the route calculations done by all the other routers in the IGP domain. When LDP session is fully established, the link is advertised with a normal cost. In the interim packets may still be sent via another link (which is probably higher cost) but has full LDP on the path. There is also a timer which is user-configurable and will start advertising the link with normal metric/cost even though LDP has synchronized for a long time. The default though will be that the timer is set to infinity.

Limitations?

This feature will only work in a straightforward manner on P2P interface or atleast interfaces that have only one LDP neighbor. When we have a multi-access interface, there can be multiple IGP neighbors downstream. Each neighbor could be a nexthop for a particular prefix and this will be known only after SPF computation. For some neighbors we may have full LDP, while some are not still fully established. However the link advertisement needs to be done on a per link basis. So it becomes an implementation decision whether to wait for all LDP peers to be fully connected before the link returns to normal cost.

LDP as of today does not have a mechanism to signal an end of LIB transfer. So after a LDP session is established a calculated guess needs to be made about when the label database transfer will complete. This will depend on the volume of the database and is usually a configurable option in the routers.

References

Cisco http://www.cisco.com/en/US/docs/ios/mpls/configuration/guide/mp_ldp_igp_synch.pdf

Juniper http://www.juniper.net/techpubs/software/erx/junose81/swconfig-bgp-mpls/html/mpls-config14.html

RFC 5443 http://www.ietf.org/rfc/rfc5443.txt

OSPF stub areas, NSSA and default routes

2011-04-30T05:35:00.001-07:00

Stub Area

From the list of LSAs given in the earlier post, it would be clear that AS external routes, such as those redistributed from BGP are flooded across the OSPF domain as Type-5 LSAs and summary of routes within an area are flooded using Type-3 LSAs. For some routing topologies, it may be unnecessary to store the complete database as illustrated below.

In the above scenario Area 2 does not have to bother about the external routes and needs to always send those packets to ABR1. However if you consider routers in Area 1, they need to make to decision whether to send the packets to Area 0 via ABR2 or to ASBR1, so they need to maintain the Type-5 LSAs in their database. So for saving memory and processing power on routers in Area 2, it is configured as a stub area. This means ABR1 does not forward either Type-3 or Type-5 LSAs into the neighbors in the area.
Whenever a network is configured as stub, the Hello packet E bit is reset. Two routers can become hello adjacent only if the bit matches, this is to prevent two routers in an area having different notions about being a stub area.
It is obvious that a backbone area cannot be configured as stub.
Also ASBRs cannot be supported into stub areas.

NSSA

There is another variation of the stub area called Not-So-Stubby-Area (NSSA). The need for an NSSA is that in some instances it is required for the area to process the external information that is injected from BGP/RIP through an ASBR attached to it but it does not really care about Type-3/5 LSAs injected from other areas. For example, in the above topology, if suppose Area2 was also connected to an ASBR as this,

External routes –> ASBR2 - Area 2 – ABR1 – Area 0 – ABR2 – Area 1 – ASBR1 <– External routes

Now Area 1 and Area 2 would need to process the external routes that are injected by their corresponding ASBR but they are not really bothered about the other ASBR in the domain that is injecting the routes because they have only one ABR. In such cases the area is configured as an NSSA. NSSA areas inject external routes as Type-7 LSAs into the area. The ABR of an NSSA converts the Type-7 LSA into a Type-5 LSA before flooding it to other areas.

These are the points to note when converting the LSAs and flooding.

Not all Type-7 LSAs are converted and flooded. This is because some ASBR injected routes may be relevant only within the area and some routes like default route should not be propagated. There is a N/P (propagate) bit in the LSA that indicates whether this route needs to be propagated.
There could be multiple ABRs in the NSSA and each of them will receive the Type-7 route but only the ABR with the highest router ID performs the translation.

Default Routes

In the above cases of stub and NSSA we know that we need to use the default route while routing packets from the stub/NSSA areas, which brings up the question of how the default routes are generated within OSPF. The following link should answer the question, ie. it is basically configured to do so.

How does OSPF generate default route – Cisco

We need to understand that there may be more than one ABR connected to the stub/NSSA areas and they can both be advertising default routes. The one among them is chosen using normal cost based rules.

OSPF link state advertisement and acknowledgement

2011-04-30T05:34:00.001-07:00

LSA Types

For a brief description of all the LSA types refer this.

LSA aging

Let us briefly describe how link state information is aged. The LS age that is present in the LS header counts from 1 up. When the age of an LSA reaches one hour it is removed from the router’s database. The LSA is required to be refreshed normally every 30 minutes. Also as seen earlier, an LS is not updated more frequently than every 5 seconds. It is possible that a router that advertised an LSA dies, in which case it takes an hour for the information to be flushed out. It is possible for a originating router to flush out the LSA from the system by advertising it with Age 0 at any time.

OSPF database synchronization between neighbors

2011-04-30T05:33:00.001-07:00

LSA Header

There are basically two portions to every LSA, a header which is 20 bytes long which uniquely identifies the LSA using a combination of and a LS type specific portion. The contents of the LSA header area:

LS Age
Options
LS Type
Link State ID
Advertising Router
LS sequence number
LS checksum
Length

Database description packet

When routers become hello adjacent, the router generates a database description packet (DDP) that contains the LSA headers of all the LSAs it has.
Each DDP has a sequence number and is individually acknowledged by the neighbor. The neighbor can send back its own data in the acknowledgement. Unless an ack is received the next DDP packet is not sent.
The final DDP packet is a blank packet just for ack purposes.

LS Request and Update

The receiving router examines every LSA header and looks at the sequence number of the LSA. If it already has the LSA but with a lower sequence number or if it doesnt have the LSA at all, it sends a LS Request packet for that specific LSA.
The LSA sequence numbers are linear increasing numbers. The sequence number starts at 0x80000001 which is the least negative number (it is signed) and then increases until max positive number. Since routers are not allowed to regenerate an LSA more frequently than 5 seconds, it will take about 600 years for the sequence number to run out.
On identifying the LSAs that are needed from the neighbor the router sends out the following LS Request packet, identifying each LSA by . It does not specify the instance as the LSA could have changed between the last DDP and now.

OSPF hello establishment on broadcast and p2p links

2011-04-30T05:32:00.001-07:00

In this part we will look at OSPF neighbor establishment.

When Hello packets are successfully exchanged between two directly connected routers, they become neighbors (partially adjacent). They become fully adjacent when their databases are synchronized.
In a broadcast network, if every node needs to become a neighbor of every other node, then we need n * (n-1) / 2 adjacencies and databases need to be synchronized in all the adjacencies. To avoid this, one of the routers in the network is elected as a Designated Router (DR) and adjacencies are formed between all the routers in the network and the DR alone. This will result in only n-1 adjacencies. To handle the eventuality of DR going down and a new DR election taking place, causing disruption to protocol working, a Backup Designated Router (BDR) is also elected. All routers have a adjacency formed with the BDR as well, hence with a BDR there are 2n-1 adjacencies in a network.
OSPF transmits a Hello packet on all enabled interfaces periodically (default: 10 seconds). When OSPF does not receive a Hello packet from a neighbor for 4x Hello interval, it deems that the neighbor is dead and starts rerouting traffic away from the failed node. However there exist other mechanisms such as BFD to detect failures faster than the OSPF Dead interval.
OSPF respects IP subnet model, hence if the network mask does not match between two routers, hello adjacency does not come up between them. Router priority is used in DR election. If a router does not wish to be considered in DR/BDR election it should advertise itself with a priority of 0.The hello interval and dead interval can be tweaked during advertisement to a value that is possibly higher than the default, this will result in lesser message exchange but higher dead neighbor detection time.
OSPF hello packets are always sent to AllSPFRouters (224.0.0.5) to which all OSPF enabled interfaces listen to.

OSPF primer

2011-04-30T05:31:00.000-07:00

In a series of posts, we will look at the different aspects of Open Shortest Path First (OSPF) algorithm and its working in a little bit of detail.

History

OSPF is an IETF defined routing protocol. Even though ISO committee was working on IS-IS at the same time, IS-IS at that time was not deemed fit for a IP based routing protocol as IS-IS was run in Layer 2 and there were no extensions for IP in it (at that time). Also it didnt make use of IP features such as fragmentation and reassembly, multicast address etc. at that time. It is a different story that IS-IS also evolved a lot under the IETF and is another primary IGP today but IETF wanted full control over the specification of a IP based IGP and the goal was achieved with OSPF which became the most popular IGP as far back as 1992. OSPFv2 is the standard for IPv4 OSPF. When IPv6 came along, OSPFv3 was defined that specifically catered to IPv6 alone. There are only a few functional differences between OSPFv2 and OSPFv3 though and we will examine them as well.

Highlights

OSPF runs directly over IP, it has a protocol number of 89.
OSPF uses a combination of Djikstra’s Shortest Path First Algorithm (SPF) and distance vector algorithm (otherwise known as Bellman-Ford).
OSPF is a hierarchial routing protocol, it splits the entire routing domain into different areas and runs SPF separately for each area. For intra-area route calculation SPF is used and for inter-area routes, distance vector algorithm is used.
OSPF defines a common high level architecture for identifying neighbors and distributing network information that can be used for the route calculation but specifies different mechanisms for handling different types of networks such as point-to-point networks, broadcast networks, NBMA networks and point-to-multipoint networks.

Operation

An OSPF domain is split into multiple areas, there is a special area known as the backbone area which binds together all areas. The routers that connect to more than one area are called Area Border Routers (ABR). An area must have an ABR that floods information into the backbone area. However it is possible that the ABR is not directly connected to the backbone area but attaches to another ABR via a virtual link to flood its area information into the backbone area.
A set of directly connected routers can form an adjacency by using Hello packets.
Once two neighbors have communication setup, they exchange their local Link State database with each other using Database Description packets and Link State packets. Link state information that is generated by a router will contain its local interface information plus information that is re-distributed into OSPF by other routing protocols such as RIP and BGP.
By means of a concept called reliable flooding, it is ensured that the database is completely synchronized across the whole network.
SPF is now run on the database to compute the routes to different networks and installed in the RIB. The SPF calculation is only for intra-area, for inter-area a distance vector method is used.
Any change in the network topology will regenerate a LSA which is again reliably flooded across the network and SPF is rerun.

We will look at the above steps in more detail in subsequent posts.

Can we use GRE tunnel for L3VPN?

2011-04-30T05:27:00.000-07:00

The answer is yes and RFC 4797 describes the use of GRE or IP tunnels instead of a MPLS based tunnel for implementing Layer 3 VPNs.

Motivation

In the MPLS/BGP IP VPN model, the ingress PE, egress PE as well as the transit P routers need to be MPLS aware. However there may be scenarios where are non-MPLS aware P routers in a network over which a MPLS/IP-VPN must run. This RFC addresses this particular condition with a less secure IP/GRE based tunnel solution.

Operation

In the usual MPLS/BGP VPN model, MP-BGP runs between the PE endpoints and distributes the VC label for a particular VRF route. After this label is pushed onto the packet, there is an outer label that is pushed that belongs to a RSVP or LDP tunnel that runs from the source PE to the destination PE. In the model described in the RFC, the operation of the protocol until the inner label is pushed is the same as traditional L3 MPLS based VPNs. However beyond that instead of pushing the packet with a RSVP/LDP label, the packet is encapsulated in a IP or GRE tunnel. It is possible to copy the QoS properties from the inner packet to the outside label as well to ensure preferential treatment. So this is basically MPLS over IP or MPLS over GRE. The transit P routers forward the packet only based on the IP/GRE header and are not required to be MPLS capable.

Security

In the traditional model packets arriving at a egress PE come in with a label and the PE can validate that the packet is indeed arriving with the label that is distributed to its immediate upstream neighbor. However in the IP tunnel model, the packets arriving are plain IP packets which are susceptible to being spoofed.

How to calculate bandwidth per slot?

2011-04-30T05:26:00.000-07:00

There are recent announcements of a 250Gbps per slot product from Juniper and a CRS-1 successor from Cisco that is 120Gbps per slot. At this point we must understand that there are different “maths” for doing this. Here are a few links that throw more light on the issue.

Rules for stating bandwidth on Cisco and competitive switches.

Lets talk bandwidth

Here is a gist/example of how bandwidth capacity of a slot is done:

Every switch fabric has a channel capacity (say 3.125 Gbps full duplex)

Each switch fabric has multiple channels going to a single slot (say 2, which means there is 6.25 Gbps capacity)

Each slot is connected to multiple switch fabrics at the same time depending on the architecture, say this is 10. Hence each slot has access to 62.5Gbps bandwidth full duplex per slot. There are some companies which state this as 125Gbps because they count 62.5Gbps in IN direction and 62.5Gbps in out direction at the same time.

Each fabric has a total number of channels it can support. In above case we had 10 slots with 2 channels to each slot, so a minimum of 20 channels has to be supported by the fabric. Assume that the fabric has capacity for more channels (for any future expansions) and it can support 26 channels. Then the switching capacity of the fabric is 125Gbps * 26 = 3.25Tbps. Note that here we have taken the full duplex into account.

Cut-through and store-and-forward switching

2011-04-30T05:22:00.000-07:00

When packets are forwarded by a ASIC or an FPGA based L2/L3 switch, there are fundamentally two different models that can be used. In the first, the entire packet is received from the incoming port and buffered, the ASIC/FPGA instructions are executed over the packet in one shot depending on or multiple level TCAM matches. The packet is then modified and sent out of the egress port, this model is known as store and forward architecture. The main advantage of this model is that because it inherently supports buffering, it can support cases where there is a speed mismatch between the ingress and egress ports (ingress being more). The main disadvantage is that there is an inherent latency involved in the model.

In some environments such as HPC or in data centers, it is possible that the latency (which could be in the order of microseconds) is not acceptable. There are also cases where there may be a huge network consisting of switches at multiple levels and hence the latencies will add up and the aggregate number is too large (such as in trading environments). To address these, there is an an alternative model of switching known as cut-through switching, in which the packet is not buffered and is switched as soon the relevant headers are inspected. There may be configurations, such as ACL, which may require more fields in the header to be examined before a decision is taken. Also it is possible that packets with errors in FCS are also forwarded because FCS appears at the end of the packet. However these are minor issues considering that the latency can be reduced to be order of nano seconds.

Cisco link describing the two models of switching:

http://www.cisco.com/en/US/prod/collateral/switches/ps9441/ps9670/white_paper_c11-465436.html

Arista 7100 series data sheet supporting 600 ns latency (Uses Fulcrum)

http://www.aristanetworks.com/en/products/7100series

Juniper EX2500 supporting 700ns latency (uses Fulcrum)

http://www.juniper.net/us/en/products-services/switching/ex-series/ex2500/#specifications

Blade technologies Rackswitch G8124 again supporting 700ns latency using Fulcrum

http://www.bladenetwork.net/RackSwitch-G8124.html

Force10 S2410 switch supporting 300ns latency

http://www.force10networks.com/products/s2410.asp

Brocade TurboIron 24x supporting 1.5 microsecond latency

http://www.brocade.com/products-solutions/products/ethernet-switches-routers/enterprise-mobility/product-details/turboiron-24x-switch/overview.page

VPLS architecture

2009-06-11T01:16:00.000-07:00

I will get around soon to writing a few notes here about VPLS architecture as I am still learning about it. But pasting the link to the document that has a very good description about it.

http://www.exponential-e.com/PDF/whitepapers/VPLS-Technical-Tutorial.pdf

Kompella and Martini

2009-06-11T01:02:00.000-07:00

Both Draft-Martini and Draft-Kompella were the starting points for defining Layer-2 VPN architectures.

Draft-Martini utilizes LDP to establish a point-to-point Layer-2 VPN over a MPLS backbone, it does not talk anything about auto-discovery.

Draft-Kompella utilizes BGP for both signalling and auto-discovery to establish fully meshed (multipoint) pseudowires for L2VPN over MPLS backbone.

Draft-Martini was standardized into RFC 4906 (which is now historic) and it has been superseeded by PWE2 working group documents RFC 4447 and related ones. Draft-Kompella expired and was never made into an RFC.

The documents later evolved into 3 sets of documents:
RFC4447 and related documents standardized by PWE3 group
RFC4761 Virtual Private LAN Service (VPLS) Using BGP for Auto-discovery and Signaling by Kireeti Kompella and Yakhov Rekhter
RFC 4762 Virtual Private LAN Service (VPLS) Using BGP for Auto-discovery and Signaling by Marc Lasserre and Vach Kompella

A more detailed description of the above evolution is given here
http://networkers-online.com/blog/2009/01/draft-martini-draft-kompella-and-l2vpn-services/

Need to set BOS bit for LDP untagged operation

2009-06-10T22:57:00.000-07:00

Consider a case of LDP untagged operation, ie. a downstream router has not advertised a label for a particular prefix. Now if we receive a packet with 2 labels and the outer label matches our incoming label for this particular prefix, then the normal operation is to remove the outer label and forward the packet to the IGP selected neighbor. Which of course in this case has not advertised any label as yet. However this should not be done, because the downstream neighbor may or may not have a proper entry for the bottom label that will not be exposed.

If the downstream neighbor were really interested in receiving the bottom label (customer label) and switch based on that, it should have advertised implicit null (3). Since it has not done that, we cannot expose the inner label to it. So for all such cases where the outgoing label is untagged, we must check bottom-of-stack (BOS) bit. Only if it is set we can forward the packet after popping top label.

This is a typical scenario where LDP is running in the core and there are pseudowire LSPs running beneath it with customer labels. Incase the LDP path is broken in between the core cloud, this will prevent packets from getting forwarded with incorrect label within the core.

RSVP protocol

2009-06-10T22:20:00.000-07:00

Introduction

RSVP is a resource reservation protocol. It tries to reserve resources in the forward path between a source and a receiver or multiple receivers. It is not a routing protocol by itself but can work with any routing protocol to find paths that match a resource requirement and also reserve resources along the path that is computed.

RSVP is receiver oriented, it is the receiver which initiates and refreshes the resource reservation. RSVP is a soft state protocol, so reservations have to be refreshed in periodic intervals. Resource reservation can use one of different styles defined by RSVP. There is scope for future extension of styles as well. The Qos parameters that are reserved are opaque to RSVP, its job is to only carry the reservation request and verify if the request can be satisfied by the router.

The different reservation styles that are currently defined are described below. Before we get to that we must understand the following terms.

Filter spec
Assume there are n senders sending data flows to a particular receiver. A filter spec identifies the specific sender or senders for whom to apply this resource reservation. So in the above case there can be n distinct filter specifications based on the sender IP address. A sender port number can also be used as an additional distinguishing parameter for filter spec.

Flow spec
A flow specification gives the QoS parameters that are to be reserved for a particular session. These parameters as I already mentioned are totally opaque to RSVP. From the above definition of filter spec, we must be able to understand that for every filter spec there is a flow spec and that filter spec could be for one or many senders.

Wildcard Filter
There are no separate filterspec specifications for distinguishing between senders here. All senders for a particular flow share the largest reservation that is made on the router. The merged request that is sent to upstream neighbors (there may be two upstream neighbors if two Path messages were received for same flow), contains the largest allocation that is required downstream taking into account all the downstream interfaces.

Fixed-Filter Spec
In this model, distinct reservations are made for every on the outgoing interface, but if there are more than one outgoing interface for the same filterspec, then the same reservation is used for both. When the reservation requests are sent upstream, every distinct filterspec generates a separate reservation request, that is the maximum of the filter-spec that is received on all outgoing interfaces.

Shared-Explicit Spec
Here the different filter-specs of the same flow share the same reservation on the outgoing interfaces. When the reservation requests are merged and sent upstream, the requests are sent to upstream neighbors that sent the Path messages for that particular and that is the merge of all senders for that flow irrespective of the requirement of that particular sender.

RSVP basics

2008-06-10T22:01:00.000-07:00

RSVP reserves resources in a network for a particular traffic flow.

A flow is generally identified by
+ Destination address
+ Protocol identifier
+ Optionally a destination port.

RSVP Path Message:
# Path messages are sent by the sender of the traffic to the actual destination address of the stream.
# These contain the RA option causing the intermediate routers along the path to inspect the packet and create
a Path State Block for the packet.
# Path messages contain a Sender Template which is exactly similar to Filter Specification and can contain a
maximum of sender IP address and TCP/UDP port optionally. They inherit the protocol from the session.
# Contain a Sender Tspec and an Adspec.

Types of RSVP classes:
+ Null (Need not be implemented), Session, Rsvp_Hop, Time_Values,
+ Style, Flowspec, Filter_Spec, Sender_Template,
+ Sender_Tspec, Adspec, Error_Spec, Policy_Data (not defined yet),
+ Integrity, Scope and Resv_Confirm
Each class has its own set of C-types which can for example be used to distinguish between IPv4 and IPv6.