Jaycee's Networking

August 14, 2009

Switching Algorithms/Paths

Filed under: Information, IOS — Tags: — Jaycee @ 4:17 am

A. Overview:

1. Switching – the process of moving packets from one interface to another whinin a router.

2. Routing – the process of choosing paths and forwarding packets to destinations outside of the physical router.

3. Switching Algorithm – a valuable way to increase or decrease a router’s performance.

4. RIB (Routing Information Base) –

1) is built by L3 routing protocols
2) is essentially the routing table
3) The decisions about how to move packets from one interface to another are based on the RIB.

5. Steps of the process of switching a packet:

1) Determine whether the packet’s destination is reachable

2) Determine the next hop to the destination, and to which interface the packet should be switched to

3) Rewrite the MAC header on the packet to reach its destination

6. Requirements of router switching:

a. Interfaces have access to input/output memory. When a packet comes into an interface, the router must decide to which interface the packet should be sent. Once the decision is made, the packet’s MAC header are rewritten, and the packet is sent on its way.

b. Packets must get from one interface to another.

c. How the router decides which interface to switch the packet to – is based on the switching path in use.

d. Routing table contains all the necessary information to determine the correct interface, but process switching must be used to retrieve data from the routing table.

B. Process Switching:

1. It’s the original method of determining which interface to forward a packet to.

2. The processor calls a process that accesses the RIB, and waiting for the next scheduled execution of that process to run.

3. Steps for Process Switching:

process switching

1) The interface processor detects a packet and moves the packet to the input/output memory.

2) Interface processor generates a receive interrupt.

a. CPU(Central processor) determines the packet type (IP), and copies it to the processor memory if necessary.

b. Then the processor places the packet on the appropriate process’s input queue and releases the interrupt.

c. The process for IP packets is titled ip_input.

3) When the scheduler next runs, it notices the presence of a packet in the input queue for the ip_input process, then schedules the process for execution.

4) When the ip_input process runs, it looks up the next hop and output interface information in the RIB. Then it consults the ARP cache to retrieve the L2 address for the next hop.

5) The process rewrites the packet’s MAC header with the appropriate addresses, then places the packet on the output queue of the appropriate interface.

6) The packet is moved from the output queue of the outbound interface to the transmit queue of the outbound interface.

=> then Outbound QoS

7) The output interface processor notices the packet in its queue, and transfers the packet to the network media.

4. Slowness happens at:

slowness on process switching

a. The processor waits for the next scheduled execution of the ip_input process.

b. ip_input process references the RIB when it runs

1) ip_input process is at the same priority level as other processes on the router, such as routing protocol and HTTP web server interface.

2) Packets sourced from or destined to the router itself are always process-switched, such as SNMP traps from the router and telnet packets destined for the router.

C. Interrupt Context Switching:

1. The processor interrupts the current process to switch the packet.

interrupt context switching

2. It’s faster than process switching since ip_input process is rarely called. Interrupt Context Switching usually bypasses the RIB, and works with parallel tables, which are built more efficiently.

3. Steps for Interrupt Context Switching:

1) The interface processor detects a packet and moves the packet into input/output memory.

2) The interface processor generates a receive interrupt. During this time, the CPU determines the packet type (IP) and begins to switch the packet.

3) The processor searches the route cache for: destination reach-ability,  output interface, next hop, MAC conversion. Then the processor uses this information to rewrite the packet’s MAC header.

4) The packet is copied to either the transmit or the output queue of the outbound interface. The receive interrupt is ended, and the originally running process continues.

5) The output interface processor notices the packet in its queue, and transfers the packet to the network media.

4. RIB is by passed entirely in this model. The necessary information is retrieved from “route cache“. Each switching path has its own means of determining, storing, and retrieving this information. There are 3 different methods:

a. Fast Switching:

fast-switching binary tree

1)  uses binary tree format for recording/retrieving information in the route cache.

2) The information of the next hop and MAC address changes is stored within each node.

3) It’s fast compared with searching the RIB since the tree is very deterministic.

4) Drawbacks:

4.1) The data for each address is stored within the  nodes, the size of the data is not static. Each node may be a different size, the table can be inefficient.

4.2) Route cache is updated only when packets are process-switched. The route cache is updated only when the 1st packet to a destination is switched. To keep the data in the route cache current, 1/20th of the entire route cache is aged out (discarded) every minute. This table must be rebuilt using process switching.

4.3) ARP table is not directly related to the contents of the route cache. Process switching must be used when ARP changes.

b. Optimum switching:

optimum-switching multiway tree

1) uses a multiway tree instead of a binary tree for recording/retrieving information in the route cache

2) This pattern continues for 4 levels – one for each octet.

3) The information of each route (prefix) or IP address is stored within the final node.

4) The size of the table can be variable since each node may or may not contain information.

5) Drawbacks:

5.1) Searching the tree is not as efficient as it might be if every node were of a known static size.

5.2) The relevant data is stored in the nodes and has no direct relationship to the RIB or ARP cache, entries are aged and rebuilt through process switching.

c. Cisco Express Forwarding (CEF):

CEF forwarding and adjacency tables

1) CEF is the default switching path on all modern routers.

2) The data is not stored within the nodes. Each node becomes a pointer to another table, which contains the data.

3) Each node is the is the same static size w/o data but the position of the node is a reference to adjacency table.

4) Adjacency table stores the pertinent data, such as MAC header substitution and next hop information for the nodes.

5) Advantages:

5.1) Both forwarding table and adjacency table are built w/o process switching

5.2) Forwarding table is built separately from the adjacency table, an error in one table doesn’t cause the other to become stale.

5.3) When the ARP cache changes, only the adjacency table changes, so aging or invalidation of the forwarding table is not required.

5.4) CEF supports load balancing over equal-cost paths.

D. Configuring and Managing Switching Algorithm (or Paths):

1. Process Switching:

R0# sh ip int vlan 301 | i switching
 IP fast switching is enabled
 IP fast switching on the same interface is disabled
 IP Flow switching is enabled
 IP CEF switching is enabled
 IP Selective flow switching turbo vector
 IP Flow CEF switching turbo vector
 IP multicast fast switching is enabled
 IP multicast distributed fast switching is disabled
 IP multicast multilayer switching is disabled

a. To disable all Interrupt Context Switching Paths, use command:

R0(config-if)# no ip route-cache
R0#sh ip int vlan 301 | i switching
 IP fast switching is disabled
 IP fast switching on the same interface is disabled
 IP Flow switching is disabled
 IP CEF switching is disabled
 IP Selective flow switching turbo vector
 IP Flow CEF switching turbo vector
 IP multicast fast switching is disabled
 IP multicast distributed fast switching is disabled
 IP multicast multilayer switching is disabled

b. When a router is process switching most of its IP packets, the top process will always be ip_input. You can verify this by the command:

R0# sh proc cpu sorted | e 0.00
CPU utilization for five seconds: 49%/26%; one minute: 45%; five minutes: 45%
PID Runtime(ms)   Invoked      uSecs   5Sec   1Min   5Min TTY Process
281   3118803922583781382          0 26.95% 24.53% 21.42%   0 IP Input
178     2276332   5264619        432  0.15%  0.08%  0.03%   0 SNMP ENGINE

2. Fast Switching:

To enable fast switching:

R0(config-if)# ip route-cache
R0#sh ip int vlan 301 | i swi
 IP fast switching is enabled
 IP fast switching on the same interface is enabled
 IP Flow switching is disabled
 IP CEF switching is disabled
 IP Selective flow switching turbo vector
 IP Flow CEF switching turbo vector
 IP multicast fast switching is enabled
 IP multicast distributed fast switching is disabled
 IP multicast multilayer switching is disabled

=> Turning on fast switching is NOT enabling CEF.

3. CEF:

a. CEF is enabled by default.

b. There are 2 places that it con be configured:

R0(config)# ip cef
R0(config-if)# ip route-cache cef

c. CEF will load-balance packets based on a per-destination by default. => A single destination will use the same link

d. CEF allows you to configure load balancing on a per-packet basis. => VoIP cannot tolerate per-packet load balancing because packets may arrive out of order. When using usch protocols, always ensure that load balancing is performed per-destination, or use a higher-level protocol such as Multilink-PPP.

R0(config-if)# ip load-sharing per-packet
R0(config-if)# ip load-sharing per-destination

e. To show CEF tables:

R0# sh ip cef
Prefix              Next Hop             Interface
0.0.0.0/0           192.168.4.14          Vlan301
0.0.0.0/32          receive
127.0.0.0/8         attached             EOBC0/0
127.0.0.0/32        receive
127.0.0.51/32       receive
127.255.255.255/32  receive
192.168.4.0/28       attached             Vlan301
192.168.4.0/32       receive
192.168.4.1/32       receive
192.168.4.12/32      192.168.4.12          Vlan301
192.168.4.13/32      192.168.4.13          Vlan301
192.168.4.14/32      192.168.4.14          Vlan301
192.168.4.15/32      receive
224.0.0.0/4         drop
224.0.0.0/24        receive
255.255.255.255/32  receive
Advertisements

4 Comments »

  1. well said, awesome!!

    Comment by Akhmad Kun — August 15, 2009 @ 11:09 pm

  2. The DNS and mx records are a hierarchical naming system for computers, services, or any resource participating in the Internet.

    Comment by phyncdyed — September 2, 2009 @ 9:46 am

  3. I need some knowladge in TCP/UDP ports.
    I’m looking for info about prt 37849, but tcp port range library have few info. Any advice?

    Comment by TypeWheefly — September 8, 2009 @ 3:07 pm


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: