Showing posts with label misc - routing. Show all posts
Showing posts with label misc - routing. Show all posts

Monday, April 9, 2012

Cisco IOS Packet Switching Architectures

Cisco IOS packet switching algorithms (or paths) are the most foundation components of Cisco routers. Different switching methods and structures affect how a router performs its primary task.

In Ethernet, switching is the process of forwarding frames based on destination MAC addresses. In routers, switching is the process of forwarding packets between interfaces within a router.

Packet switching is responsible for moving packets across a router. Its most basic operations are:
  1. A packet is received from an inbound interface.
  2. The packet’s destination address is inspected and compared against the routing table.
  3. If there is a match, the packet is forwarded out to the appropriate outbound interface.
  4. If there is no match, the packet is discarded or dropped.
The main concern of IOS is not much on how to switch packets, but how to switch them quickly. Packet switching is a data-intensive operation as opposed to a computation-intensive operation. Speeding up the operation is not as simple as using a faster CPU. Other factors, eg: I/O bus and memory technology, can also have big impact on the packet switching performance.

The challenge of IOS developers is to create the highest possible performance based on the limitations of the given CPU, I/O bus, and memory technology.

Process switching was the only switching method when IOS was first developed. Later IOS releases introduced newer improved switching methods. Some methods reply on hardware-specific optimizations while other use software techniques that work well on many platforms.

Below lists the switching methods developed and available as of Cisco IOS release 12.0:
  1. Process Switching
  2. Fast Switching
  3. Autonomous Switching
  4. Silicon Switching Engine (SSE) Switching
  5. Optimum Switching
  6. Distributed Fast Switching
  7. Cisco Express Forwarding (CEF)
  8. Distributed Cisco Express Forwarding (dCEF)
This chapter covers only 4 of these methods in detail – process switching, fast switching, optimum switching, and Cisco Express Forwarding. Autonomous and SSE switching are platform-specific and aren’t commonly used in today’s networks. Distributed fast switching is actually an implementation of optimum switching on intelligent line cards.


Process Switching

Process switching is available on every version of IOS, and every platform. Its main disadvantage against other switching architectures is its speed, as it is required to perform routing table lookup for every packet and has the least amount of performance optimizations, and consumes large amounts of CPU resources. However, it has the advantage of being platform-independent and provides some load balancing capabilities not found in other switching methods.

Process Switching

Below lists the steps for process switching:
  1. The network interface processor detects there is a packet on the network media that needs to be processed. It receives and transfers the packet to the I/O memory.
  2. The interface processor generates a receive interrupt which interrupts the processor and inform it that there is a received packet waiting in I/O memory that needs to be processed. The IOS interrupt handler inspects the packet’s header information (eg: encapsulation type, network layer header) to determine packet type, and copies it into the processor memory if necessary (platform dependant). The processor then places the packet on input queue of the appropriate switching process and releases the interrupt. The switching process for IP packets is called ip_input.
  3. During the next time the scheduler runs, it notices the presence of a packet in the input queue for the ip_input process, and schedules the process for execution.
  4. The actual packet forwarding operation begins when the ip_input process runs. It consults the RIB (routing table) to determine the next-hop address and the output interface, and then consults the ARP cache to retrieve the corresponding physical layer address for the next-hop.
  5. The ip_input process rewrites the MAC header of the packet with the appropriate addresses, and places the packet on the output queue of the appropriate outbound network interface. The packet is queued for transmission.
  6. The packet is moved from the output queue of the outbound interface to the transmit queue of the outbound interface. Any outbound QoS operation takes place between these two queues.
  7. The output interface processor detects a packet in its transmit queue and waiting for transmission. It dequeues the packet and transmits it onto the network media.
  8. After the output interface processor transmitted the packet, it interrupts the processor to inform that the packet has been transmitted. IOS then updates the outbound packet counters and frees or releases the space in I/O memory formerly occupied by the packet.
The key points in the process that make it slow is that the processor waits for the next scheduled execution of the ip_input process; and when the ip_input process finally runs, it refers the RIB – a very slow process. The ip_input process is run at the same priority level as other processes, eg: routing protocols, and the HTTP web server interface. Process switching should never be used as the switching method of choice. Other methods produce significantly better performance.

Packet sourced from or destined to the router itself, eg: SNMP traps from the router and Telnet packets destined for the router, are always process-switched.

Load Balancing with Process Switching

One of the advantages of process switching is per-packet load balancing, which provides a simple way to route traffic over parallel paths to a destination – packets are distributed among the available paths based on the routing metric (or path cost) assigned to each path. The metric or cost is used to calculate a load share counter, which actually determines which path to take.

Note: Some applications, eg: VoIP, cannot tolerate per-packet load balancing because packets may arrive out of order and affect the processing of the data. Always ensure that load balancing is performed on a per-destination basis when the network is supporting such applications.

Equal Cost Path Load Balancing

Below shows that RT1 has 2 equal cost paths to the 10.1.3.0/24 network. The asterisk character (*) next to one of the paths indicates the path that will be used for the next packet switched toward 10.1.3.0/24. The traffic share count on both paths is 1, which means packets are switched out each path in a round-robin basis.
RT1#sh ip route 10.1.3.0 255.255.255.0
Routing entry for 10.1.3.0/24
  Known via "static", distance 1, metric 0
  Routing Descriptor Blocks:
  * 10.1.1.2
      Route metric is 0, traffic share count is 1
    10.1.2.2
      Route metric is 0, traffic share count is 1

RT1#

IGRP and EIGRP can install unequal cost paths into the routing table. Figure A2-3 below shows a modified setup in Figure A2-2, with the upper path has about twice the bandwidth of the other.

Unequal Cost Path Load Balancing

Below shows RT1 has 2 unequal cost paths to the 10.1.3.0/24 network. The lower-cost path through 10.1.1.1 has a traffic share count of 2, while the higher-cost path through 10.1.2.1 has a traffic share count of 1. In such a way, for every 2 packets switched out the higher-cost path, 1 packet is switched out the lower-cost path, as indicated by the packet numbers in the figure.
RT1#sh ip route 10.1.3.1
Routing entry for 10.1.3.0/24
  Known via "eigrp 100", distance 90, metric 1538560, type internal
  Redistributing via eigrp 100
  Last update from 10.1.2.2 on Serial0/1, 00:02:15 ago
  Routing Descriptor Blocks:
  * 10.1.1.2, from 10.1.1.2, 00:02:15 ago, via Serial0/0
      Route metric is 1538560, traffic share count is 2
      Total delay is 20100 microseconds, minimum bandwidth is 2500 Kbit
      Reliability 255/255, minimum MTU 1500 bytes
      Loading 1/255, Hops 1
    10.1.2.2, from 10.1.2.2, 00:02:15 ago, via Serial0/1
      Route metric is 3074560, traffic share count is 1
      Total delay is 20100 microseconds, minimum bandwidth is 1000 Kbit
      Reliability 255/255, minimum MTU 1500 bytes
      Loading 1/255, Hops 1

RT1#

Although per-packet load balancing gives the most even distribution across parallel paths, it has a significant drawback – it does not preserve packet order, packets can arrive out of order due to the varying latency and delay factors throughout the various routing paths. Out-of-order packet processing can significantly degrade system performance, reduce TCP session throughput, loss of data in some UDP-based protocols (eg: SNA or NetBIOS Fast Sequenced Transport (FST), or Voice-over-IP – VoIP), and might be even interpreted as attacks by some firewalls.

As mentioned earlier, the main disadvantage of process switching is its speed. Process switching requires routing table and ARP cache lookup for every packet, the time required to perform a lookup grows along with the sizes of the routing table and ARP cache. Recursive routes also require additional lookups in the routing table.

Another factor that affects the speed of process switching is in-memory data transfer time. On some platforms, packets must be copied between I/O memory and processor memory before and after the switching process. Memory data copy operations are very CPU intensive.

Fast Cache was deployed to overcome the speed limitation of process switching. It allows IOS to have smaller lookup tables, switches packets during the packet receive interrupt, and removes the need for in-memory data copying.


Interrupt Context Switching

Interrupt context switching is another switching method that is much faster than process switching. Below are the main differences between interrupt context switching and process switching:
  1. The current process is interrupted to perform packet switching. Packets are switched during the packet receive interrupt, rather than the scheduled ip_input process. The ip_input process is rarely called, and the processor no longer has to wait for a process to complete.
  2. The processor uses route cache to find all the information needed to switch the packet. The type of route cache being used and the contents in the cache depend on the router hardware and the type of interrupt content switching – fast switching, optimum switching, or Cisco Express Forwarding (CEF).
  3. Cache entries are built by the ip_input process while packets are first process switched. The first packet sent to a destination will always be process switched. Subsequent packets to the same destination can be fast switched and the scheduled ip_input process does not get involved in switching the packets as long as the cache entry exists.
A cache is a special high-speed storage mechanism used to store some frequently access data. A cache has smaller size or capacity, higher speed, and more expensive than normal main memory. It is being used to achieve higher performance as applications can access frequently access data in a faster manner compared to accessing the slower main memory.

Interrupt Context Switching

Below are the steps of interrupt context switching and how cache is being used in the switching process:
  1. The network interface processor detects there is a packet on the network media that needs to be processed. It receives and transfers the packet to the I/O memory.
  2. The interface processor generates a receive interrupt. During the interrupt, the IOS interrupt handler determines the packet type, and then begins the switching process.
  3. The process consults the route cache to determine the next-hop address, the output interface, and the MAC header for the next-hop (used for rewriting the MAC header of the packet). Note: A cache entry is built by the ip_input process during the first lookup process.
  4. The packet is copied to either the output or transmit queue of the outbound interface depends upon various factors. The receive interrupt is ended, and the originally running process continues.
  5. The output interface processor detects a packet in its transmit queue and waiting for transmission. It dequeues the packet and transmits it onto the network media.
  6. After the output interface processor transmitted the packet, it interrupts the processor to indicate that the packet has been transmitted. IOS then updates the outbound packet counters and frees or releases the space in I/O memory formerly occupied by the packet.
Notice that the ip_input process never gets involved when switching the packet. The currently running process is interrupted, instead of waiting for the next scheduled execution of the ip_input process. No scheduled process is involved when a packet is fast switched as long as a cache entry exists. IOS can now perform the entire packet switching operation with very short period of an interrupt using Fast Cache! Caching allows IOS to separate the resource-intensive task of making a routing decision from the relatively easy task of forwarding a packet. Fast switching introduced the concept of “route once, forward many times”.

The show ip cache verbose EXEC command displays the routing table cache for fast switching.
RT1#sh ip cache verbose
IP routing cache 2 entries, 344 bytes
   5 adds, 3 invalidates, 0 refcounts
Minimum invalidation interval 2 seconds, maximum interval 5 seconds,
   quiet interval 3 seconds, threshold 0 requests
Invalidation rate 0 in last second, 0 in last 3 seconds
Last full cache invalidation occurred 00:00:32 ago

Prefix/Length           Age       Interface       Next-hop
10.1.3.1/32-24          00:00:30  Serial0/1       10.1.2.2
                   4   0F000800
192.168.1.2/32-24       00:00:30  FastEthernet1/0 192.168.1.2
                   14  CC020F400000CC000F4000100800

RT1#
RT1#sh arp
Protocol  Address          Age (min)  Hardware Addr   Type   Interface
Internet  192.168.1.1             -   cc00.0f40.0010  ARPA   FastEthernet1/0
Internet  192.168.1.2             1   cc02.0f40.0000  ARPA   FastEthernet1/0
RT1#

Unlike the master tables that used to build the caches, which are basically just big lists, caches are implemented with well organized data structures to achieve fast retrieval of a particular entry with minimal search operations. The searching time increases proportionately with the size of the table for the master tables; while the searching time for the caches can be kept small and fairly constant regardless of the total number of entries.

The IP Fast Cache was first implemented as a data structure called hash table. In Cisco IOS Release 10.2, it was replaced with another data structure called 2-way radix tree, a form of binary tree. A radix tree stores the forwarding information and MAC headers based on the binary representation of the key (the unique field that uniquely identifies each set of data). The binary tree can have up to 32 levels, corresponding to the bits within an IP address.

Below shows the steps of searching a number throughout a binary tree:
  1. Start from the left (the most significant bit) of the binary number to be searched for.
  2. Begin at the root of the tree, branch left or right in the tree based on that digit.
  3. Compare the next digit until reaching an end node.
The Fast Switch Binary Tree
- For visualizing purpose, the nodes that marked in grey in the figure above match an IP address of 170.x.x.x (the binary value of 170 is 10101010).

The benefit of this design is speed when compared with searching the RIB, as information regarding the next-hop and MAC address changes is stored within each end node, and finding specific entries is very quick since the tree is very deterministic.

The route cache is not directly related to the routing table, and it is updated only when packets are being process-switched. To keep the entries in the route cache current and from losing their synchronization with the routing table and ARP cache, as well as to keep unused entries in the fast cache from unduly consuming memory on the router, 1/20th of the route cache is aged out or discarded randomly every minute. Those entries must then be rebuilt through process switching.

And since there is no correlation between the MAC headers (used for rewrites) in the ARP cache and the structure of the fast cache, when the ARP table changes, some portion of the fast cache must be invalidated and rebuilt through process switching.


Traffic Load Sharing with Fast Switching

Fast switching does not support load sharing on a per-packet basis, which could lead to uneven link utilization in some situations where multiple paths exist between 2 destinations. This lack of a deterministic load balancing scheme is a concern for many network designers. Newer switching algorithms, eg: Cisco Express Forwarding (CEF), now support load balancing schemes that overcome this problem.

Load sharing with fast switching occurs on a per-destination basis. When there are multiple equal cost paths for a particular destination network, fast cache has an entry for each host reachable within that network, and all traffic destined for a particular host follows a particular link.


Optimum Switching

Optimum switching is basically fast switching with some caching optimizations. As like fast switching, optimum switching performs the entire packet switching process during a single packet receive interrupt. The main difference between fast and optimum switching is the way that the route cache is accessed. The optimum switching code is also developed to take advantages of certain processor architectures; while the fast switching code is generic, and is not optimized for any specific processor. Unlike fast switching that utilizes binary tree that is designed to support any type of value, optimum switching is available only for the IP protocol.

Optimum switching utilizes a 256-way multiway tree instead of a binary tree to record and retrieve information in the route cache. For IP addresses, a multiway tree is much faster because each octet can only be one of 256 values.

Optimum Switching 256-way Multiway Tree

The root branches into 256 nodes numbered 0 to 255. Each node then branches into an additional 256 nodes. This pattern continues for 4 levels, one for each octet in the IPv4 addressing. The nodes in grey show how an IP address (3.253.7.5) would be matched. This type of tree is much faster for IP address lookups than a binary tree because the table is optimized for the IP address format. Information for each route (prefix) or IP address is stored in the final node. Since the size of this information is variable and each node may or may not contain information, the overall table size is also variable; and this is a drawback – searching the tree is not as efficient as it might be if every node were of a known static size.

Since the information stored in the nodes has no direct relationship to the RIB and ARP cache, the entries are also aged out and rebuilt through process switching as like with fast switching.

Optimum switching is available only on high-end routers, eg: Cisco 7500 and 7600 series.


Cisco Express Forwarding (CEF)

Cisco Express Forwarding (CEF) is the preferred switching path on any router that supports it and is the default switching path on all modern routers.

CEF introduces the concept of a trie (the forwarding table – FIB) upon the optimum switching multiway tree, in which the data is not stored within the nodes, but rather each node that is the same size becomes a pointer to another table – the adjacency table, that contains the data, eg: next-hop information and MAC header, that are needed to perform packet switching. The forwarding table is built from the routing table; while the adjacency table is built from the ARP table, Frame Relay map table, or other L2 table types.
Note: The term trie comes from the word retrieve, and is pronounced like tree or try.
Note: The terms CEF forwarding table, Forwarding Information Base (FIB) and CEF table are being used interchangeably for many CEF-related texts.

CEF Forwarding Table and Adjacency Table

One of the biggest advantages of CEF is that the forwarding and adjacency tables are built without process switching – without waiting for a packet to be sent to a destination, in fact the tables are built before any packets are switched. Additionally, the forwarding table is built separately from the adjacency table – an error in one of the tables does not cause the other to become stale. When the ARP cache changes, only the adjacency table changes, therefore aging and invalidation of the forwarding table is no longer necessary. The CEF entries in the forwarding table never age, as they are linked directly to the routing table, changes upon the dynamic routing table are immediately propagated to the forwarding table.

The adjacency table contains information other than MAC header and outbound interface as below:
  • cached – a prebuilt MAC header rewrite string and outbound interface used to reach a particular adjacent host or router.
  • receive – Packets destined to this IP address should be received by the router, which includes broadcast addresses and IP addresses configured on the router itself.
  • drop – Packets destined to this IP address should be dropped, which includes traffic denied by an access list, or routed to the NULL interface.
  • punt – Packets that Cisco Express Forwarding cannot switch and will be passed to the next best switching algorithm for processing – normally fast switching.
  • glean – The destination is directly connected, but there is no prebuilt MAC header rewrite string currently available. An ARP request must be sent to build the MAC header.

Below shows how CEF build the appropriate adjacency table entry from the ARP cache information for a directly connected destination – 192.168.1.2 that is resolved to a glean adjacency.
RT1#sh ip cef detail
IP CEF with switching (Table Version 16), flags=0x0
  6 routes, 0 reresolve, 0 unresolved (0 old, 0 new), peak 2
  3 instant recursive resolutions, 0 used background process
  9 leaves, 11 nodes, 12664 bytes, 18 inserts, 9 invalidations
  0 load sharing elements, 0 bytes, 0 references
  universal per-destination load sharing algorithm, id B02A5381
  2(0) CEF resets, 0 revisions of existing leaves
  Resolution Timer: Exponential (currently 1s, peak 1s)
  1 in-place/0 aborted modifications
  refcounts:  3078 leaf, 3072 node

  Table epoch: 0 (9 entries at this epoch)

0.0.0.0/0, version 0, epoch 0, attached, default route handler
0 packets, 0 bytes
  via 0.0.0.0, 0 dependencies
    valid no route adjacency
0.0.0.0/32, version 0, epoch 0, receive
192.168.1.0/24, version 5, epoch 0, attached, connected
0 packets, 0 bytes
  via FastEthernet1/0, 0 dependencies
    valid glean adjacency
192.168.1.0/32, version 3, epoch 0, receive
192.168.1.1/32, version 2, epoch 0, receive
192.168.1.255/32, version 4, epoch 0, receive
224.0.0.0/4, version 1, epoch 0
0 packets, 0 bytes, Precedence routine (0)
  via 0.0.0.0, 0 dependencies
    next hop 0.0.0.0
    valid drop adjacency
224.0.0.0/24, version 2, epoch 0, receive
255.255.255.255/32, version 1, epoch 0, receive
RT1#
RT1#debug ip cef table
IP CEF table debugging is on
RT1#
RT1#debug arp
ARP packet debugging is on
RT1#
RT1#ping 192.168.1.2

Type escape sequence to abort.
Sending 5, 100-byte ICMP Echos to 192.168.1.2, timeout is 2 seconds:

00:10:10: IP ARP: creating incomplete entry for IP address: 192.168.1.2 interface FastEthernet1/0
00:10:10: IP ARP: sent req src 192.168.1.1 cc00.0550.0010,
                 dst 192.168.1.2 0000.0000.0000 FastEthernet1/0
00:10:10: IP ARP: rcvd rep src 192.168.1.2 cc02.0550.0000, dst 192.168.1.1 FastEthernet1/0
00:10:10: CEF-IP: Checking dependencies of 192.168.1.0/24
00:10:10: CEF-Table: Adjacency-prefix 192.168.1.2/32 add request -- succeeded.
00:10:12: IP ARP: rcvd req src 192.168.1.2 cc02.0550.0000, dst 192.168.1.1 FastEthernet1/0
00:10:12: IP ARP: sent rep src 192.168.1.1 cc00.0550.0010,
                 dst 192.168.1.2 cc02.0550.0000 FastEthernet1/0.!!!
Success rate is 60 percent (3/5), round-trip min/avg/max = 16/25/40 ms
RT1#
RT1#sh ip cef detail
IP CEF with switching (Table Version 17), flags=0x0
  7 routes, 0 reresolve, 0 unresolved (0 old, 0 new), peak 2
  3 instant recursive resolutions, 0 used background process
  10 leaves, 11 nodes, 12800 bytes, 19 inserts, 9 invalidations
  0 load sharing elements, 0 bytes, 0 references
  universal per-destination load sharing algorithm, id B02A5381
  2(0) CEF resets, 0 revisions of existing leaves
  Resolution Timer: Exponential (currently 1s, peak 1s)
  1 in-place/0 aborted modifications
  refcounts:  3080 leaf, 3072 node

  Table epoch: 0 (10 entries at this epoch)

Adjacency Table has 1 adjacency
0.0.0.0/0, version 0, epoch 0, attached, default route handler
0 packets, 0 bytes
  via 0.0.0.0, 0 dependencies
    valid no route adjacency
0.0.0.0/32, version 0, epoch 0, receive
192.168.1.0/24, version 5, epoch 0, attached, connected
0 packets, 0 bytes
  via FastEthernet1/0, 0 dependencies
    valid glean adjacency
192.168.1.0/32, version 3, epoch 0, receive
192.168.1.1/32, version 2, epoch 0, receive
192.168.1.2/32, version 16, epoch 0, connected, cached adjacency 192.168.1.2
0 packets, 0 bytes
  via 192.168.1.2, FastEthernet1/0, 0 dependencies
    next hop 192.168.1.2, FastEthernet1/0
    valid cached adjacency
192.168.1.255/32, version 4, epoch 0, receive
224.0.0.0/4, version 1, epoch 0
0 packets, 0 bytes, Precedence routine (0)
  via 0.0.0.0, 0 dependencies
    next hop 0.0.0.0
    valid drop adjacency
224.0.0.0/24, version 2, epoch 0, receive
255.255.255.255/32, version 1, epoch 0, receive
RT1#

The following packets are sent or punted to the CPU for process switching:
  • ARP requests and replies
  • IP packets that require a response from a router, eg: TTL has expired, MTU is exceeded, fragmentation is needed, etc.
  • IP broadcasts that will be relayed as unicast, eg: DHCP requests, IP helper address functions.
  • Routing protocol updates.
  • Cisco Discovery Protocol packets.
  • Packets requiring encryption.
  • Packets triggering Network Address Translation.
  • Other non-IP protocol packets, eg: IPX, AppleTalk, DECnet, etc.
The version number indicates the number of times the CEF entry has been updated since the CEF table was generated. The epoch number indicates the number of times the CEF table has been flushed and regenerated as a whole.

CEF supports load balancing over equal-cost paths. Load balancing at the switching level is far superior by load balancing via routing protocols, as routing protocols operate at a higher level. CEF load balancing is performed on a per-destination basis by default – all packets for a destination will use the same link. CEF can be configured to perform load balancing on a per-packet basis, for scenarios such as there is only a single host on the other end of the links, or there is a single server that consumes the majority of the bandwidth for any single link.

Issue the ip load-sharing [per-packet | per-destination] interface subcommand to enables per-packet or per-destination CEF load balancing for an interface. When enabling per-packet load balancing to a particular destination, all interfaces that can forward traffic to the destination must be enabled for per-packet load balancing.
Note: The ip load-sharing per-destination interface subcommand is the default configuration and is not shown in the configuration files.

Sunday, April 8, 2012

Cisco IOS Architecture

General Operating System Concepts
Modern operating systems provide 2 primary functions:

Hardware Abstraction Provides software developers a common interface between their applications and the hardware, which shields the programmers from the complexity of the hardware. The hardware-specific codes are developed once in the OS and shared by everyone.
Resource Management Managing the hardware resources (eg: CPU, memory, disk space) so that they can be shared efficiently among multiple applications. Like hardware abstraction, the resource management codes are developed in the OS to keep application programmers from reinventing the wheels – writing the resource management codes.

Multitasking is referred to as running multiple programs at once. Applications written for multitasking OSes often contain multiple independent and concurrent tasks, called threads. Each thread has its own set of CPU register values, but can share the same memory address space with other threads belong to the same application (or process). A process is a group of threads that share a common memory space and have a common purpose. On OSes and CPUs that support virtual memory, each process runs in a separate address space that is protected from other processes.

A processor can execute instruction for only one program at a time. Scheduling decides which process or thread should run. This function is usually performed by the core of the OS – kernel. An OS can use one of the several scheduling methods to schedule threads, depends on the type of applications (eg: batch, interactive, real-time). Different types of applications have different CPU utilization characteristics, and the overall performance is affected by the scheduling method used.

FIFO with run-to-completion is the simplest scheduling method where each thread is assigned to the processor in the order its run request is received and let all threads run to completion. It is easy to implement, has very low overhead, and fair – all threads are treated equally. First come, first served.

FIFO with run-to-completion scheduling is good for batch applications that perform serial processing and then exit, but it does not work well for interactive and real-time applications, which require fast and short duration access to the CPU to provide quick response to users or other devices. A possible scheduling method for these applications is priority scheduling, where priorities are assigned to different types of threads – critical threads, eg: real-time threads are assigned with a higher priority then other less critical threads, eg: batch threads. Multiple threads with the same priority are then processed in the order which they were received (FIFO).

Even though priority scheduling is an improvement over FIFO, it still has one drawback that makes it unsuitable for interactive and real-time applications – high-priority threads can get stuck behind a long running low-priority thread. A method that can temporarily suspend or preempt a running thread to allow other threads to access the CPU is required to solve this problem.

Thread Preemption is the ability of an OS to involuntarily suspend a running thread to allow another higher priority thread to access the CPU resources. Preemptive multitasking OSes employ preemptive scheduling methods that utilize preemption instead of run-to-completion.

Preemption relies on the kernel to periodically change the current thread via a context switch, which can be triggered with either a system timer (each thread is assigned a time slice) or a function call to the kernel. When a context switch is triggered, the kernel selects the next thread to run and queue the preempted thread in a list for it to run again at its next opportunity – the computer actually changes the task that it is currently working on.

Context switching can be quite expensive in term of system performance as all processor registers for the thread that is being taken off must be saved, and all processor registers for the thread that is being granted access to the CPU must be restored.
Below describes the advantages and disadvantages of preemptive multitasking:

Advantages
Disadvantages
Predictable. A thread can be set up to run once a second and the programmer can be reasonably certain that the thread will be scheduled to run at that interval. Less efficient. It tends to switch contexts more often, and the CPU spends more time for scheduling and switching between threads than run-to-completion approach.
Difficult to break. No single thread can monopolize the CPU for long period and stop other threads from running. Adds complexity to applications. A thread can be interrupted anywhere. Applications must be well designed and written to protect critical data structures from being changed by other threads when they are being preempted.

OSes also manage the memory resources by dividing them into various sections for storing actual application instruction codes, variables, and heap. The heap is a section of memory from which processes can dynamically allocate and free the memory resources.

Virtual memory is found in most modern OSes to provide more memory than the available physical RAM size, and is transparent to processes. The computer memory is expanded with secondary storage, eg: harddisk drive. Virtual memory is created using a hardware feature that available on some CPUs – memory map unit (MMU). MMU automatically remaps memory address requests to either physical memory (RAM) or secondary storage (harddisk) depends on where the contents actually reside. MMU can be programmed to create separate address spaces for all processes to prevent them from accessing the memory address space of other processes.

Segmentation > A running process is restricted to use certain parts of memory called segments. If a process read, or write data outside the permitted memory address space or virtual memory (paging) allocated for it, a general protection fault or page fault will occur respectively.

Although virtual memory has many benefits, but there are resource requirements and performance penalties. As a result, IOS is not implemented with a full virtual memory scheme.

OSes usually support interrupts, a hardware feature that cause the CPU to temporarily suspend its current instruction sequence and transfer control to a special program called interrupt handler. OSes usually provide a set of interrupt handlers for all possible interrupt types.


Cisco IOS Architecture

The main challenge for IOS is to switch or forward packets as quickly and efficiently as possible.

IOS is a specialized embedded operating system tightly coupled to the underlying hardware. Therefore always consider the hardware architecture when discussing about the software.

Cisco IOS has a monolithic architecture (a single large program), which means it runs as a single image and all processes share the same memory address space. There is no memory protection mechanism exists due to the CPU and memory overhead they introduce – a bug in a process can potentially corrupt the data and/or memory of another process.

Cisco IOS has a run-to-completion scheduler – the kernel does not preempt a running process. A process must make a kernel call to allow other processes to run. For Cisco routers that require very high availability and response time, eg: Cisco CRS-1, these limitations are not acceptable. Competitive network OSes (eg: Juniper JUNOS) were designed not to have these limitations.

A new version of Cisco IOS – IOS-XR was developed to offer modularity, memory protection, lightweight thread, and preemptive scheduling.

IOS software modularity is a new IOS feature that supports individually restartable process. Past patches would require a complete IOS update and system reboot, whereas the new modular kernel allows the affected processes to be patched independently. After patching, the particular processes can be restarted independently from other processes, hence reduces system downtime.

Microcode is a set of processor-specific software instructions that enables and manages the features and functions of a specific processor type. A router loads the microcode for each processor type present in the system upon system startup or reload. The latest available microcode image is bundled and distributed along with the system software image.

Memory Organization

IOS maps the entire physical memory into a large flat virtual address space. Since the kernel does not perform any memory paging or swapping, the virtual address space is limited to the available physical memory. IOS divides the address space into various areas called regions that correspond to the various types of physical memory, eg: SRAM and DRAM. Classifying memory into regions allows IOS to group various types of memory and therefore the software does not need to know about specific types of memory on every platform.

Memory regions can also be nested in a parent-child relationship. Although there is no imposed limit upon the depth of nesting, only one level is really used. Nested regions form subregions of the parent region. Subregions are denoted by a name with the : separator and no parentheses.
Memory regions are classified into the following 8 categories:

Memory Region Class Characteristics
Local Normal run-time data structures and local heaps. Often in DRAM.
Iomem Shared input / output memory that is visible to both the CPU and controllers of network interfaces. Often is DRAM.
Fast Fast memory, eg: SRAM for speed-critical tasks and special purpose.
IText A region for the code currently executed by the IOS.
IData Storage for the initialized variables.
IBss Storage for non-initialized variables. BSS – Block Storage Section.
PCI Peripheral Component Interconnect (PCI) memory accessible to all devices on the PCI bus.
Flash Flash memory. Often used to store configuration backups, the binaries of IOS images, and other data, eg: crash info.
A file system is typically built in the Flash memory region.

The show region privileged command displays the regions defined on a system.
Router#sh region
Region Manager:

      Start         End     Size(b)  Class  Media  Name
 0x0B000000  0x0BFFFFFF    16777216  Iomem  R/W    iomem
 0x60000000  0x6AFFFFFF   184549376  Local  R/W    main
 0x600089A4  0x643611BF    70617116  IText  R/O    main:text
 0x64362000  0x6621F9BF    32233920  IData  R/W    main:data
 0x6621F9C0  0x66A471BF     8550400  IBss   R/W    main:bss
 0x66A471C0  0x67A471BF    16777216  Local  R/W    main:heap
 0x67A47218  0x68A47217    16777216  Local  R/W    main:heap
 0x6A000000  0x6AFFFFFF    16777216  Local  R/W    main:heap
 0x7B000000  0x7BFFFFFF    16777216  Iomem  R/W    iomem:(iomem_cwt)
 0x80000000  0x8AFFFFFF   184549376  Local  R/W    main:(main_k0)
 0xA0000000  0xAAFFFFFF   184549376  Local  R/W    main:(main_k1)


Free Region Manager:

      Start         End     Size(b)  Class  Media  Name
 0x68A47270  0x69FFFFA7    22777144  Local  R/W    heap


Router#

The gaps between the address space, eg: iomem ends at 0x0BFFFFFF and main begins at 0x60000000, are intentional to allow for expansion of the regions and provide protection against errant threads. If a runway thread is advancing through memory and writing garbage into a free unallocated memory region (the gap), it will be stopped.

The entire DRAM area from 0x60000000 to 0x6AFFFFFF is classified as a local region and further divided into subregions that correspond to the various parts of the IOS image itself (text, BSS, and data) and the heap. The heap is the entire free Local memory that left over after the IOS image was loaded into it.

Below shows that some regions appear to be duplicates with different address ranges.
0x0B000000  0x0BFFFFFF    16777216  Iomem  R/W    iomem
 0x7B000000  0x7BFFFFFF    16777216  Iomem  R/W    iomem:(iomem_cwt)
These duplicate regions are called aliases. Some Cisco platforms have multiple physical address ranges that point to the same block of physical memory. These different ranges are used to provide alternate data access method or automatic data translation in hardware.
For example, one address range might provide cached access to an area of physical memory while another might provide uncached access to the same memory.

The duplicate ranges are mapped as alternate views during system initialization and IOS creates alias regions for them. Aliased regions do not count toward the total memory on a platform, as they are not really separate memory! They allow IOS to provide a separate region for alternate memory views without artificially inflating the total memory calculation.

IOS Processes

An IOS process is equivalent to a single thread in other OSes – IOS processes have only one thread each. Each process has its own memory block (stack) and CPU context (eg: registers), and can control resources such as memory and a console device. IOS does not implement virtual memory protection between processes in order to minimize the overhead of paging or swapping. No memory management is performed during context switches; therefore, although each process receives its own memory allocation, other processes can freely access the same memory space – nothing can stop a process from intruding into a memory block of another process! Cisco has sacrificed both stability and security features in the IOS architecture design to achieve higher productivity and reduce resource consumptions.

Processes can be created and terminated anytime by the kernel (during IOS initialization) or by another running process while IOS is operating except during an (hardware) interrupt. When the CPU is interrupted, it temporarily suspends the execution of instructions of the current thread and begins to run an interrupt handler function. New processes cannot be created while the CPU is running the interrupt handler.

The parser is responsible for creating many of the IOS processes. The parser is a set of functions that interpret IOS configuration and EXEC commands. It is invoked by the kernel during IOS initialization and EXEC processes that are providing a CLI to the console and Telnet sessions. Anytime a command is entered by a user or a configuration line is read from a file, the parser interprets the text and takes immediate action. Some commands result in setting of a value, eg: an IP address; while others enable complicated functionality, eg: routing or event monitoring.

Some commands result in starting a new process, eg: when the router eigrp command is entered via the CLI, the parser starts a new process called ipigrp if it has not already been started.

Device Drivers

A primary OS function is provides hardware abstraction between platform hardware and the programs that run on it. Hardware abstraction typically occurs in device drivers that are part of the OS, making them an integral part of the system. IOS contains device drivers for a range of platform hardware devices, eg: Flash cards and NVRAM, but most notable are the device drivers for network interfaces.

IOS network interface device drivers provide the primary intelligence for packet operations in and out of interfaces. Each driver consists of a control component and a data component. The control component is responsible for managing the state and status of the device, eg: shutting down an interface; while the data component is responsible for all data flow operations through the device and contain logic that assists with the packet switching operations. IOS device drivers are very tightly coupled with the packet switching algorithms.

IOS device drivers interface with the rest of the IOS system via a special control structure called Interface Descriptor Block (idB). The idB contains entry points into the functions of a device driver and data about the state and status of a device, eg: the IP address, the interface state, and the packet statistics are some of the fields in the idB. IOS maintains an idB for each interface present on a platform and maintains an idB for each subinterface.

Friday, January 20, 2012

IP SLA (Service-Level Agreement)

The Cisco IOS IP Service-Level Agreement (IP SLA) feature allows Cisco customers to analyze and measure IP service levels for IP applications and services, to increase productivity, to lower operational costs, and to reduce network outages. The measurement can be as simple as using ICMP ping packets to determine if an IP address responds, or as sophisticated as measuring the jitter (inter-packet delay variance) of VoIP packets that flow through a particular path.

Service provider customers can use IP SLA to measure and provide service level agreements; while enterprise customers can use IP SLA to verify the outsourced service level agreements, and understand network performance for both existing and new IP applications and services. IP SLA provides improvements over the traditional Layer 2 SLA to provide a broader scope to support end-to-end sophisticated and accurate application-aware performance measurements.

Various IP SLA operations provide useful measurement statistics for network assessments, verifying Quality of Service (QoS), easing the deployment of new IP applications and services, designing networks, problem analysis, and network troubleshooting.

IP SLA generates traffic in a continuous, predictable, and reliable manner to measure network performance. IP SLA performs active monitoring by generating and analyzing traffic to measure performance either between Cisco IOS devices or between a Cisco IOS device and a normal application server. IP SLA uses unique service level assurance metrics and methodology to provide highly accurate, precise service level assurance measurements.

IP SLA sends data across the network to measure performance between multiple network locations or across multiple network paths. It simulates network data and IP services, and collects network performance information in real time. The information collected includes round-trip response time, one-way latency, jitter (inter-packet delay variance), packet loss, packet sequence, voice quality scoring, network resource availability, application performance, server response time, and download time.

The statistics collected by IP SLA operations are stored in both CLI and SNMP MIBs that can be assessed using the CLI or SNMP through the Cisco Round-Trip Time Monitor (RTTMON) and SYSLOG Management Information Bases (MIBs). Network management systems such as CiscoWorks Internetwork Performance Monitor (IPM) and other 3rd party Cisco partner performance management products are able to collect the statistics data using SNMP and generate reports to justify whether a network has reached the SLAs defined for it.

IP SLA mainly uses operations for its operation. Each operation defines the packet type to be generated, the source and destination addresses, and other characteristics of the packets. The configuration includes the time-of-day when the router should generate the packets, the types of statistics that should be gathered, and how often the packets should be generated. A single router can be configured with different types of IP SLA operations.
Note: IP SLA has origins in earlier IOS, including the Response Time Reporter (RTR) feature. The RTR feature uses the term probe to refer to what IP SLA refers to as an operation.

An IP SLA operation is able to send packets to any IP address, whether it is a router or a host. When sending to a host, no special software or configuration is required on the host; indeed the IP SLA operation send operational packets only to the native services on the host, eg: ICMP echo requests, TCP connection requests, or even HTTP GET requests to a web server. The server will try to respond to these requests.

The Operation of IP SLA

An IP SLA operation can also send packets to another router that acts as an IP SLA responder, which provides a wider range of possible operation types. An IP SLA responder responds to IP SLA request packets that a router would not normally respond to, providing a way to monitor network behavior without introducing dedicated probes around the network to test the network. Ex: An IP SLA operation could send Real-time Transport Protocol (RTP) packets that have the same content as VoIP packets to an IP SLA responder. The IP SLA responder replies the packets back to the IP SLA operation as if a voice call exists between the 2 routers.

Below list the various types of IP SLA operations:
 Dynamic Host Configuration Protocol (DHCP)
 Data Link Switching Plus (DLSw+)
 Domain Name System (DNS)
 File Transfer Protocol (FTP)
 Hypertext Transfer Protocol (HTTP)
 ICMP Echo and ICMP Path Echo
 ICMP Jitter and ICMP Path Jitter
 Transmission Control Protocol (TCP) Connect
 UDP Echo and UDP Jitter
 VoIP gatekeeper registration delay
 VoIP post-dial delay
 VoIP Real-time Transport Protocol (RTP)

Below are the general steps to configure an IP SLA ICMP Echo operation:
Step 1) Create the IP SLA operation and assign it an integer operation number using the ip sla {sla-ops-num} global configuration command.
Step 2) Define the IP SLA operation type and the parameters for that operation type. For ICMP Echo, define the source (optional) and destination IP addresses or hostnames using the icmp-echo {dest-ip-addr | dest-hostname} [source-ip {src-ip-addr | src-hostname} | source-interface {intf-type intf-num}] IP SLA operation subcommand.
Step 3) (Optional) Define a (non-default) frequency that the IP SLA operation should send the packets using the frequency {seconds} IP SLA subcommand. The default frequency is 60 seconds.
Step 4) Schedule the IP SLA operation to run for a period to gather statistics using the ip sla schedule {sla-ops-num} [life {forever | seconds}] [start-time {hh:mm[:ss] [month day | day month] | pending | now | after hh:mm:ss}] [ageout seconds] [recurring] global configuration command.

Static routes and PBR can be configured to utilize the capabilities of IP SLA operations upon controlling the usages of the static and PBR paths based upon the failure or reduced performance (based on the configured threshold) of a particular measurement.

This section describes the concepts of IP SLA and along with its configuration in enough depth for influencing static routes and policy routing. Below implements an ICMP echo operation, which requires configuration only on one router, with no IP SLA responder. The remote router or host replies to the IP SLA ICMP Echo Requests just like any other ICMP Echo Requests.

IP SLA Echo Operation

Note: The configuration is enhanced so that small ping packets sent between PC1, PC2, and RT1 as well as EIGRP Hellos packets between 11.11.11.1 and 11.11.11.2 are not being policy routed.

Below shows the process of implementing an ICMP Echo operation on RT1 with the purpose to test the PBR route through the secondary path – 22.22.22.0/30. The operation is configured to:
 Send ICMP Echo Requests to RT2 E0/0 – 172.16.1.1).
 Use the secondary IP address of RT1 E0/0 (192.168.2.1) as the source IP address.
 Send the packets every 10 seconds.
 Start the operation immediately, and run it forever.
 Enable local policy routing on RT1 for the locally originated IP SLA ICMP Echo operation packets to flow through the secondary path.

Configuring an IP SLA ICMP Echo operation on RT1:
RT1#conf t
Enter configuration commands, one per line.  End with CNTL/Z.
RT1(config)#ip sla 1
RT1(config-ip-sla)#icmp-echo 172.16.1.1 source-ip 192.168.2.1
RT1(config-ip-sla-echo)#frequency 10
RT1(config-ip-sla-echo)#exit
RT1(config)#ip sla schedule 1 life forever start-time now
RT1(config)#ip local policy route-map RM-PBR

The parameters of the icmp-echo IP SLA subcommand acts as an extended ping from the CLI, which it specifies both the source and destination IP addresses.

The show ip sla configuration [sla-ops-num] EXEC command displays the configuration details including all the default values for all IP SLA operations or a specified IP SLA operation:
RT1#sh ip sla configuration
IP SLAs Infrastructure Engine-II
Entry number: 1
Owner:
Tag:
Type of operation to perform: icmp-echo
Target address/Source address: 172.16.1.1/192.168.2.1
Operation timeout (milliseconds): 5000
Type Of Service parameters: 0x0
Vrf Name:
Request size (ARR data portion): 28
Verify data: No
Schedule:
   Operation frequency (seconds): 10  (not considered if randomly scheduled)
   Next Scheduled Start Time: Start Time already passed
   Group Scheduled : FALSE
   Randomly Scheduled : FALSE
   Life (seconds): Forever
   Entry Ageout (seconds): never
   Recurring (Starting Everyday): FALSE
   Status of entry (SNMP RowStatus): Active
Threshold (milliseconds): 5000 (not considered if react RTT is configured)
Distribution Statistics:
   Number of statistic hours kept: 2
   Number of statistic distribution buckets kept: 1
   Statistic distribution interval (milliseconds): 20
History Statistics:
   Number of history Lives kept: 0
   Number of history Buckets kept: 15
   History Filter Type: None
Enhanced History:


RT1#

The show ip sla statistics [sla-ops-num] [details] EXEC command displays the current operational status and statistics for all IP SLA operations or a specified IP SLA operation:
RT1#sh ip sla statistics
IPSLAs Latest Operation Statistics

IPSLA operation id: 1
        Latest RTT: 28 milliseconds
Latest operation start time: *13:44:38.003 UTC Fri May 14 2010
Latest operation return code: OK
Number of successes: 3
Number of failures: 0
Operation time to live: Forever


RT1#
The command output shows that 3 intervals have passed, 3 ICMP Echo Requests were success with no failures; the latest round-trip time, and the return code of the most recent operation – a key value used for IP SLA tracking.

IP SLA Tracking

A static or policy route can be configured in a way that it will be used only when an IP SLA operation remains successful. The configuration introduces a tracking object that is being referenced by the static route, policy route, and IP SLA operation as shown in the figure above.

The tracking object determines its tracking state as either UP or DOWN based on the most recent return code of the IP SLA operation. The IP SLA return codes vary upon different types of IP SLA operations. The return code may be an OK meaning that the last operation is successful, in which the tracking object would result in an UP state; or other return codes for other IP SLA operations that define thresholds. The tracking operation remains in an UP state as long as the result of the IP SLA operation is within the configured threshold.

Another great usage of the tracking object is to control route flapping. Route flap occurs when a router adding and removing a route in the routing table in a very frequent manner. If a static route is being tracked by an IP SLA operation, the return code of the IP SLA operation could change upon every operation and results in a route flap. A delay can be set to determine how long a tracking object must wait to change its state upon a tracking state change.

Below lists the steps to configure a static route to track an IP SLA operation:
Step 1) Create a tracking object to an IP SLA operation using the track {obj-num} ip sla {sla-ops-num} {state | reachability} global configuration command. The state and reachability keywords track the IP SLA operation return code and whether the route is reachable respectively.
Note: This command was introduced on Cisco IOS Release 12.4(20)T.
Step 2) (Optional) Configure the delay period to regulate flapping of the tracking state using the delay {down {seconds} | up {seconds}}. The down and up keywords indicate the delay periods for the notifications of a DOWN event and an UP event respectively.
Step 3) Configure the static route using the ip route {dest-network} {subnet-mask} {next-hop-addr | outgoing-intf} track {obj-num} global configuration command.

Ex: The delay down 30 up 10 tracking subcommand indicates that the clients that are tracking the object are notified after 30 seconds and 10 seconds upon the tracking state changes from UP to DOWN and from DOWN to UP respectively.

Below implements a static route that tracks a tracking object that tracking the existing IP SLA ICMP Echo operation on RT1:
RT1#conf t
Enter configuration commands, one per line.  End with CNTL/Z.
RT1(config)#track 1 ip sla 1 state
RT1(config-track)#delay down 30 up 10
RT1(config-track)#exit
RT1(config)#
RT1(config)#ip route 172.16.2.0 255.255.255.0 11.11.11.2 track 1
RT1(config)#end
RT1#sh ip route

Gateway of last resort is not set

     172.16.0.0/24 is subnetted, 2 subnets
D       172.16.1.0 [90/30720] via 11.11.11.2, 00:04:24, FastEthernet0/1
S       172.16.2.0 [1/0] via 11.11.11.2
     22.0.0.0/30 is subnetted, 1 subnets
C       22.22.22.0 is directly connected, Serial1/0
     11.0.0.0/30 is subnetted, 1 subnets
C       11.11.11.0 is directly connected, FastEthernet0/1
C    192.168.1.0/24 is directly connected, FastEthernet0/0
C    192.168.2.0/24 is directly connected, FastEthernet0/0
RT1#
RT1#sh track
Track 1
  IP SLA 1 state
  State is Up
    1 change, last change 00:00:51
  Delay up 10 secs, down 30 secs
  Latest operation return code: OK
  Latest RTT (millisecs) 60
  Tracked by:
    STATIC-IP-ROUTING 0
RT1#

Below implements an access list on RT2 to block ICMP Echo packets which results in the IP SLA operation fails, and causes the static route to be removed on RT1. RT1 will then uses the EIGRP route to reach 172.16.2.0/24.
RT2#conf t
Enter configuration commands, one per line.  End with CNTL/Z.
RT2(config)#access-list 111 deny icmp any any
RT2(config)#access-list 111 permit ip any any
RT2(config)#int s1/0
RT2(config-if)#ip access-group 111 in
RT2(config-if)#
======================================================================
RT1#
14:13:53: %TRACKING-5-STATE: 1 ip sla 1 state Up->Down
RT1#
RT1#sh ip sla statistics
IPSLAs Latest Operation Statistics

IPSLA operation id: 1
        Latest RTT: NoConnection/Busy/Timeout
Latest operation start time: *14:13:49.927 UTC Fri May 14 2010
Latest operation return code: No connection
Number of successes: 14
Number of failures: 4
Operation time to live: Forever


RT1#
RT1#sh track
Track 1
  IP SLA 1 state
  State is Down
    2 changes, last change 00:00:07
  Delay up 10 secs, down 30 secs
  Latest operation return code: No connection
  Tracked by:
    STATIC-IP-ROUTING 0
RT1#
RT1#sh ip route

Gateway of last resort is not set

     172.16.0.0/24 is subnetted, 2 subnets
D       172.16.1.0 [90/30720] via 11.11.11.2, 00:06:18, FastEthernet0/1
D       172.16.2.0 [90/30720] via 11.11.11.2, 00:00:12, FastEthernet0/1
     22.0.0.0/30 is subnetted, 1 subnets
C       22.22.22.0 is directly connected, Serial1/0
     11.0.0.0/30 is subnetted, 1 subnets
C       11.11.11.0 is directly connected, FastEthernet0/1
C    192.168.1.0/24 is directly connected, FastEthernet0/0
C    192.168.2.0/24 is directly connected, FastEthernet0/0
RT1#
RT1#ping 172.16.2.1

Type escape sequence to abort.
Sending 5, 100-byte ICMP Echos to 172.16.2.1, timeout is 2 seconds:
!!!!!
Success rate is 100 percent (5/5), round-trip min/avg/max = 4/24/52 ms
RT1#

The earlier set action in the route map used for the PBR – set ip next-hop 22.22.22.x can be modified to use object tracking to track the availability of the next hop – 22.22.22.x using the set ip next-hop verify-availability 22.22.22.x {seq-num} track 1 action.

Below shows that when the tracking object is UP, PBR works as configured. When the tracking object is DOWN, PBR acts as if the set action does not exist, and proceed to route the packets as per the normal destination-based routing process.
Note: Similar configuration should be implemented on RT2 as well to avoid asymmetric routing.
RT1#conf t
Enter configuration commands, one per line.  End with CNTL/Z.
RT1(config)#route-map RM-PBR permit 10
RT1(config-route-map)#no set ip next-hop 22.22.22.2
RT1(config-route-map)#set ip next-hop verify-availability 22.22.22.2 1 track 1
RT1(config-route-map)#route-map RM-PBR permit 20
RT1(config-route-map)#no set ip next-hop 22.22.22.2
RT1(config-route-map)#set ip next-hop verify-availability 22.22.22.2 1 track 1
RT1(config-route-map)#end
RT1#
RT1#sh route
route-map RM-PBR, permit, sequence 10
  Match clauses:
    ip address (access-lists): 101
  Set clauses:
    ip next-hop verify-availability 22.22.22.2 1 track 1  [up]
  Policy routing matches: 24 packets, 1536 bytes
route-map RM-PBR, permit, sequence 20
  Match clauses:
    ip address (access-lists): 102
    length 1 100
  Set clauses:
    ip next-hop verify-availability 22.22.22.2 1 track 1  [up]
  Policy routing matches: 0 packets, 0 bytes
RT1#
RT1#sh track
Track 1
  IP SLA 1 state
  State is Up
    1 change, last change 00:00:47
  Delay up 10 secs, down 30 secs
  Latest operation return code: OK  Latest RTT (millisecs) 100
  Tracked by:
    ROUTE-MAP 0
    STATIC-IP-ROUTING 0
RT1#
! After applied the Block-ICMP-ACL on RT2 Serial1/0 and waited 30 seconds...
16:33:17: %TRACKING-5-STATE: 1 ip sla 1 state Up->Down
RT1#sh route
route-map RM-PBR, permit, sequence 10
  Match clauses:
    ip address (access-lists): 101
  Set clauses:
    ip next-hop verify-availability 22.22.22.2 1 track 1  [down]
  Policy routing matches: 26 packets, 1664 bytes
route-map RM-PBR, permit, sequence 20
  Match clauses:
    ip address (access-lists): 102
    length 1 100
  Set clauses:
    ip next-hop verify-availability 22.22.22.2 1 track 1  [down]
  Policy routing matches: 0 packets, 0 bytes
RT1#

Wednesday, January 18, 2012

Policy-Based Routing

Policy-Based Routing (PBR) provides organizations the flexibility to implement policies for routing and forwarding packets that go beyond the traditional destination-based routing, eg: forwarding packets through to different physical network paths based on source and destination addresses, protocol types, user applications, and the size of packets. PBR is a form of static routing that uses route maps to create a separate process that control packet forwarding in a sophisticated way by matching and changing the attributes of packets.

Below lists other general usages of PBR:
Source-based transit provider selection – Organizations can use PBR to route traffic originating from different sets of users through different Internet connections.
Quality of Service (QoS) – Organizations can provide QoS upon differentiated traffic by setting Type of Service (ToS) or IP Precedence values in the IP packet header on edge routers and use queuing mechanisms to prioritize traffic in the network core or backbone.
Cost savings. Organizations can temporary direct the bulk traffic associated with specific application to use a higher-bandwidth, high-cost link for a short period of time and resume basic connectivity over a lower-bandwidth, low-cost link for interactive traffic.
Load sharing. Organizations can distribute traffic among multiple paths based on the characteristics of the applications in addition to the dynamic load-sharing capabilities offered by destination-based routing that the Cisco IOS software has always supported.

PBRs are applied upon incoming packets. Enabling PBR causes the router to evaluate all packets arriving on the interface configured with a route map for that purpose. Packets are being processed by the data plane and forwarded to the appropriate next-hop based on the criteria defined in the route map; and therefore override the normal packet forwarding of the router.

Most Cisco routers today use Cisco Express Forwarding (CEF) by default, which causes them to match the destination address of IP packets with the CEF table instead of the IP routing table. Cisco IOS derives the CEF table from the information in the IP routing table, with much faster entry lookup as compared with using the IP routing table.

Implementing PBR is basically configures a route map and applies the route map to an interface. The PBR route map statements can be configured with permit or deny actions.
 If the action of the statement is permit, a packet that meets the match criteria is being policy routed according to the set actions.
 If the action of the statement is deny, a packet that meets the match criteria is not being policy routed and is forwarded through the normal destination-based routing.
 If a packet is not matched by any route map statement, it is not dropped implicit deny statement; it is being forwarded through the normal destination-based routing.
 If do not want to revert to the normal destination-based routing but instead want to drop all packets that are not being matched by any criteria, configure the set interface Null0 action as the last entry of the route map.
 If a packet meets the match criteria of a permit statement with no set action, it is being forwarded through the normal destination-based routing.

Policy routing does not change the destination of the traffic; it affects only the next hop to which traffic is directed prior to arrive upon the final destination.

Below lists the match commands that matter when using route maps for PBR:

match ip address {[acl-num | acl-name] | prefix-list {ip-prefix-name}} Matches incoming packets that matched by the access list or prefix list. If multiple access lists or prefix lists are specified, matching any one will result in a match and being policy routed. Standard IP ACLs are used to specify match criteria based on source address; while extended IP ACLs are used to specify match criteria based on source and destination addresses, protocol types, applications, ToS, and IP Precedence.
match length {min max} Specifies match criteria based on the packet length between the min and max values (inclusive) in bytes. The min and max values are from 0 to 2147483647 (inclusive). Time-sensitive interactive traffic often uses small packets. They can be directly to another link to prevent the terminal sessions from starving the bandwidth resources with bulky traffic that uses large packets (file transfers).

One or more of the following set actions can be specified within a single match statement to perform customized packet forwarding requirement when the match statement is satisfied. A router evaluates the following set actions applicable for PBR in the order they are presented. As soon as a destination next-hop address or interface has been chosen, other set actions that changing the destination next-hop address or interface are ignored.

One or more of the following set actions can be specified within a single match statement to perform customized packet forwarding requirement when the match statement is satisfied. A router evaluates the following set actions applicable for PBR in the order they are presented. As soon as a destination next-hop address or interface has been chosen, other set actions that changing the destination next-hop address or interface are ignored.
set ip next-hop {ip-addr} [… ip-addr] Specifies a list of IP addresses of the adjacent next-hop routers to which the packets should be forwarded. It must be the IP address of an adjacent router. When multiple IP addresses are specified, the first IP address associated with an active interface is used; the other IP addresses are tried in turn. [1]
set interface {intf-type intf-num} [… intf-type intf-num] Specifies a list of interfaces through which the packets can be routed. When multiple interfaces are specified, the first active interface is used to forward the packets; the other interfaces are tried in turn. [1]
set ip default next-hop {ip-addr} [… ip-addr] Same logic as the set ip next-hop action; however, policy routing is applied only after attempted to route the packet using the normal destination-based routing.
set default interface {intf-type intf-num} [… intf-type intf-num] Same logic as the set interface action; however, policy routing is applied only after attempted to route the packet using the normal destination-based routing.
[1] – If the PBR route does not work due to the outgoing interface is down or the next-hop address is unreachable using a directly-connected route, the packet is forwarded using the normal destination-based routing.

The default keyword significantly impacts the operation of PBR. Without this keyword configured, Cisco IOS applies PBR before trying to use the normal destination-based routing; with this keyword configured, Cisco IOS applies PBR logic only after trying to use the normal destination-based routing and no explicit route for the destination existing in the routing table. A default route is not considered as an explicit route for an unknown destination address.
 Without the default keyword – Try PBR first; but if the PBR route fails, route as usual.
 With the default keyword – Try to route as usual while ignoring any default route; if normal routing fails, use PBR.

The set interface action has no effect and is ignored if the packet is destined to a broadcast or an unknown address. This is because there is no explicit route for the destination address of the packet exists in the routing table.

PBR also provides a mechanism to mark packets using the following commands:
set ip tos [number | name] Sets the 8-bit IP ToS field in the IP packet header.
set ip precedence [number | name] Sets the IP Precedence bits in the IP packet header.

In the 8-bit IP ToS field, the 5 least-significant bits are used for setting the Class of Service (CoS); while the 3 most-significant bits are used for setting the IP Precedence – 8 possible values (0 – 7). IP Precedence is often being used when implementing QoS services, eg: Weighted Fair Queuing (WFQ) and Weighted Random Early Detection (WRED).
Below lists the numbers and names defined for the corresponding ToS and IP Precedence values:
Title:

0 | normal Sets the normal ToS.
1 | min-monetary-cost Sets the min-monetary-cost ToS.
2 | max-reliability Sets the max reliable ToS.
4 | max-throughput Sets the max throughput ToS.
8 | min-delay Sets the min delay ToS.
0 | routine Sets the routine precedence.
1 | priority Sets the priority precedence.
2 | immediate Sets the immediate precedence.
3 | flash Sets the Flash precedence.
4 | flash-override Sets the Flash override precedence.
5 | critical Sets the critical precedence.
6 | internet Sets the internetwork control precedence.
7 | network Sets the network control precedence.
The most commonly used QoS marking tool today is Class-Based Marking. PBR was one of the few tools that could be used for marking packets for this important QoS function in the past. PBR still support marking; however, most modern QoS designs ignore this capability of PBR. The IP header originally defines a ToS byte whose individual bits have been defined in various ways over the years. One such definition is the 3-bit IP Precedence field which uses the first 3 bits of the ToS byte. Back in the 1990s, the ToS byte was redefined as the Differentiated Services (DS) byte, with the first 6 bits defined as the Differentiated Service Code Point (DSCP). Most modern QoS implementations revolve around setting the DSCP field.

The ip policy route-map {map-tag} interface subcommand specifies a route map to use for policy routing on an interface. Policy-based routing is configured on the receiving interface, not on the outgoing interface from which the packets are sent.

Occasionally it may be necessary to use PBR to process packets originated by the router itself. However, such packets are not being processed and policy routed by the ip policy route-map interface subcommand, as the packets originated by the router itself do not actually enter the router through any interface. The ip local policy route-map {map-tag} global configuration command enables local policy routing to process locally originated packets using the PBR. The IP SLA section later shows an example use of this command. IP SLA causes a router to generate packets, applying PBR to such packets influence the forwarding paths of these packets.

Network Setup for Policy-Based Routing

The sample network above demonstrates the PBR configuration for the following requirements:
 EIGRP is running on RT1 and RT2. Therefore the primary path between 192.168.0.0/16 and 172.16.1.0/24 is via 11.11.11.0/30.
 Packets sent between 192.168.2.0/24 and 172.16.1.0/24 are routed via 22.22.22.0/30.
 Packets smaller than or equal to 100 bytes are routed via 22.22.22.0/30.
 Other packets are routed normally via the primary path.

Note that small ping packets sent between PC1, PC2, and RT1 are actually being policy routed! Besides that, there is a chance that the EIGRP Hello packets between 11.11.11.1 and 11.11.11.2 are also being policy routed, which will cause the flapping of EIGRP neighborship between RT1 E0/1 and RT2 E0/1. This symptom was seen on Cisco IOS Release 12.4(T) used for the IP SLA network setup later but was not seen on Cisco IOS Release 12.3 used for the network setup above. The configuration above will be enhanced to eliminate the mentioned problems.

Below shows that PC1 sends 5 ping packets that are being policy routed via 22.22.22.0/30:
PC1#ping 172.16.1.1

Type escape sequence to abort.
Sending 5, 100-byte ICMP Echos to 172.16.1.1, timeout is 2 seconds:
!!!!!
Success rate is 100 percent (5/5), round-trip min/avg/max = 64/78/88 ms
PC1#
----------------------------------------------------------------------
RT1#clear route-map counters RM-PBR
RT1#
RT1#debug ip policy
Policy routing debugging is on
RT1#
00:12:36: IP: s=192.168.1.2 (Ethernet0/0), d=172.16.1.1, len 100, FIB policy match
00:12:36: IP: s=192.168.1.2 (Ethernet0/0), d=172.16.1.1, g=22.22.22.2, len 100, FIB policy routed
--- output omitted ---
RT1#
RT1#sh route-map
route-map RM-PBR, permit, sequence 10
  Match clauses:
    ip address (access-lists): 101
  Set clauses:
    ip next-hop 22.22.22.2
  Policy routing matches: 0 packets, 0 bytes
route-map RM-PBR, permit, sequence 20
  Match clauses:
    length 1 100
  Set clauses:
    ip next-hop 22.22.22.2
  Policy routing matches: 5 packets, 570 bytes
RT1#
The show route-map {map-name} EXEC command displays configured static and dynamic route maps along with their match, set, and continue clauses.

Below shows that PC1 sends 5 ping packets that are not being policy routed via 22.22.22.0/30:
PC1#ping 172.16.1.1 size 101

Type escape sequence to abort.
Sending 5, 101-byte ICMP Echos to 172.16.1.1, timeout is 2 seconds:
!!!!!
Success rate is 100 percent (5/5), round-trip min/avg/max = 16/56/92 ms
PC1#
----------------------------------------------------------------------
RT1#
00:13:42: IP: s=192.168.1.2 (Ethernet0/0), d=172.16.1.1, len 101, FIB policy rejected(no match) - normal forwarding
--- output omitted ---

Below shows that all packets from PC2 are being policy routed via 22.22.22.0/30:
PC2#ping 172.16.1.1

Type escape sequence to abort.
Sending 5, 100-byte ICMP Echos to 172.16.1.1, timeout is 2 seconds:
!!!!!
Success rate is 100 percent (5/5), round-trip min/avg/max = 40/61/80 ms
PC2#
----------------------------------------------------------------------
RT1#
00:14:18: IP: s=192.168.2.2 (Ethernet0/0), d=172.16.1.1, len 100, FIB policy match
00:14:18: IP: s=192.168.2.2 (Ethernet0/0), d=172.16.1.1, g=22.22.22.2, len 100, FIB policy routed
--- output omitted ---
======================================================================
PC2#ping 172.16.1.1 size 101

Type escape sequence to abort.
Sending 5, 101-byte ICMP Echos to 172.16.1.1, timeout is 2 seconds:
!!!!!
Success rate is 100 percent (5/5), round-trip min/avg/max = 44/79/100 ms
PC2#
----------------------------------------------------------------------
RT1#
00:14:50: IP: s=192.168.2.2 (Ethernet0/0), d=172.16.1.1, len 101, FIB policy match
00:14:50: IP: s=192.168.2.2 (Ethernet0/0), d=172.16.1.1, g=22.22.22.2, len 101, FIB policy routed
--- output omitted ---
RT1#
RT1#sh route-map
route-map RM-PBR, permit, sequence 10
  Match clauses:
    ip address (access-lists): 101
  Set clauses:
    ip next-hop 22.22.22.2
  Policy routing matches: 10 packets, 1145 bytes
route-map RM-PBR, permit, sequence 20
  Match clauses:
    length 1 100
  Set clauses:
    ip next-hop 22.22.22.2
  Policy routing matches: 5 packets, 570 bytes
RT1#

The show ip policy EXEC command displays the route maps used for policy routing:
RT1#sh ip policy
Interface      Route map
Ethernet0/0    RM-PBR
RT1#
======================================================================
RT2#sh ip policy
Interface      Route map
local          RM-PBR
Ethernet0/0    RM-PBR
RT2#