BFS,DFS pseudo code

The post is a reading note of CLRS elementary graph algorithm chapter. The following pseudo codes are adapted versions of Breadth First Search and Depth First Search with comments.I might add some summary of the BFS,DFS attributes later.

BFS Pseudo Code

/*
Gragh Breadth First Search

the pseudo code is adapted from CLRS 3rd edition.

Color Notation :

WHITE : undiscovered vertex
GRAY  : discovered frontier vertex
BLACK : discovered non-frontier vertex
*/

subroutine BFS(Graph G,Vertex s)
{
	// Initialization of the structure
	
	# initialization of the vertexes other than s
	foreach vertex u in (G.V - s)
	{
		u.color    = WHITE
		u.distance = INFINITE
		u.parent   = NIL
	}
	
	# initialization of the vertex s
	s.color    = GRAY
	s.distance = 0
	s.parent   = NIL
	
	# initialization of the FIFO Queue
	Queue = NIL
	Queue.enqueue(s)
	
	// Traversing the Gragh in the breadth first manner
	
	while Queue != NIL
	{
	    # dequeue the frontier vertex
		u = Queue.dequeue()
	
		# iterate through the adjacent vertexes of the 
		# current frontier vertex, and check to see 
		# if the vertex hasn't been discovered yet 
	        # to prevent duplication
		foreach vertex v in G.adj[u]
		{
			if v.color == WHITE
				v.color    = GRAY
				v.distance = u.distance + 1
				v.parent   = u
			    Queue.enqueue(v)
		}
	
		# Mark the vertex u as a non-frontier discovered vertex
		u.color = BLACK 
	}
}


// the function prints the path from s to v 
// if BFS has already run on the graph G

subroutine print_path(Gragh G, Vertex s, Vertex v)
{
	if v == s
		print s
	elseif v.parent == null
		print "no path from s to v"
	else 
	# recursive call to print_path
		print_path(G,s,v.parent)

	# continuing to print the current node after the recursive calls ends
	print v
}


DFS Pseudo Code

/*
Gragh Depth First Search

the pseudo code is adapted from CLRS 3rd edition.

Color Notation :

WHITE : undiscovered vertex, the color before the time of discovery
GRAY  : discovered frontier vertex, the color between the time of discovery and finish
BLACK : discovered non-frontier vertex, the color after the time of finish
*/

subroutine DFS(Graph G)
{
    # initialization of all the vertexes in the graph
	foreach vertex v in G.V
	{
		u.color     = WHITE
		u.parent    = NIL
		u.discovery = INFINITE
		u.finish    = INFINITE
	}

    # initialization of the timer
	time = 0

    # iterate through all the vertexes in the graph
    # perform DFS-visit if the vertex color is white

	foreach vertex u in G.V
	{
		if u.color == WHITE
		DFS-VISIT(G,u)
	}
}

subroutine DFS-VISIT(G,u)
{
    // Pre-Processing of dfs visit
    # increment timer and set
    # the discovery time and coloring

	time = time + 1
	u.discovery = time
	u.color = gray

    // Core of the dfs visit
    # iterate through all the adjacent nodes
    # and recusively perform DFS-visit if the
    # vertex color is WHITE

	foreach v in G.adj[u]
	{
		if v.color == WHITE
		{
			v.parent = u
			DFS-VISIT(G,v)
		}
	}

    // Post-Processing of dfs visit
    # increment timer and set
    # the discovery time and coloring

	u.color = BLACK
	time = time + 1
	u.finish = time
}

eem based tcl script for testing ip reachability on cisco router

This post provides a script to test reachability to a list of IP addresses which you can run multiple times without entering into the tcl shell after its first creation.

Let’s first check to see the tiny script 😀

::cisco::eem::event_register_none
namespace import ::cisco::eem::*
namespace import ::cisco::lib::*

if [catch {cli_open} result] {
    error $result $errorInfo
} else {
    array set cli1 $result
}

set address_list {"1.1.1.1" "2.2.2.2"}

foreach address $address_list {
  if [catch {cli_exec $cli1(fd) "ping $address"} result] { puts "Error: $result"} else { set cmdResult $result}
  puts "*****  Reachability Test for $address ****"
  puts $result
}

cli_close $cli1(fd) $cli1(tty_id)

This code should be very self-explanatory and is used to to test reachability to a list of addresses on a cisco router supporting tcl shell. In order to run it multiple times, we take leverage of the eem none event, meaning that the script gets run when you issue the command “event manager run $tcl-file-name” (note you can also simply run a tcl script with “source tcl-file-full-path-name”, here we are demonstrating it under EEM).

You need to register the script with the following command :

! Assuming you save this script as flash:/scripts/myScript.tcl
router(config)# event manager directory user policy flash:/scripts
router(config)# event manager policy myScript.tcl

// Before registering the script, you should create this file first !
To edit a file on cisco router, enter the tclsh interactive mode :

Router(tcl)# puts [open "flash:test" w+] {
> Your file content
> goes here...
> }

To view a file on cisco router, use the more command :

Router # more flash:/scripts/myScript.tcl

To run the script, use the following command :

router # event manager run myScript.tcl

This is a dry run of the tcl script with None event triggered.

!command output

*****  Reachability Test for 1.1.1.1 ****

Type escape sequence to abort.
Sending 5, 100-byte ICMP Echos to 1.1.1.1, timeout is 2 seconds:
!!!!!
Success rate is 100 percent (5/5), round-trip min/avg/max = 1/1/1 ms
Router>
*****  Reachability Test for 2.2.2.2 ****

Type escape sequence to abort.

Sending 5, 100-byte ICMP Echos to 2.2.2.2, timeout is 2 seconds:
!!!!!
Success rate is 100 percent (5/5), round-trip min/avg/max = 1/1/1 ms
Router>

a RFC reader application worth knowing

http://www.rfcreader.com/ offers a new way for viewing RFCs. As usual, the tool supports search by number or search by keyword which you will also find in the ietf.org website.

mpls

The enhancements are mainly introduced in reading experience where you have chapter bookmarks on the left sided panel and the text on the right. The even greater thing is that you can also add some comments and highlight some texts, the app will remember your action if you are login user!

Have fun in rfc reading 😀

Interacting with cisco routers with python pexpect

Brief words before you read the post: the post talks about possibilities on how you can interact cisco devices using python implementation of expect.

Background

I work in an education environment where lots of routers/switches needs to to be reset before the labs are delivered to students so that they can have a clean status to begin with, and sometimes we also want to stage the configurations so that they can start from a snapshot instead of the factory default. In order to automate all this work, I have found the pexpect to be a very handy tool to use, and the docs for the pexpect can be found at http://pexpect.readthedocs.org/en/latest/. If you haven’t read this, it’s recommended to get familiar with this library and then come back.

Notes on the Implementation

A skeleton of the script is as simple as the following.

class device: core library of the tool, a class for handling interaction with the devices

    method -> pre_process : prepares the environment before any other executions taking place
    method -> login : attempts to login to the router
    method -> enable : attempts to enable on the router
    method -> reset : attempts to factory reset the router
    method -> execute_cmd : execute cmd and capture the output
    method -> push_config : push prepared config on the router
    method -> save_config : save running config from the router
    method -> clear_line: clear line from the terminal server
    method -> post_process: tear down of the environment

all the methods can be easily implemented with the pexpect, and the key operation in all these functions is really just to expect a certain pattern and then respond with a certain command.

With this class implemented, you can then serialize the operation or concurrently run these operation with python threading library so that the repeated manual work can be eliminated. Another layer of automation is possible when you have tcl script saved on router flash, and the pexpect script can also run the tcl script in our pexpect automation.

There are also some more powerful tools, notably exscript and trigger, but with pexpect, you really can get a very easily customizable tool without understanding or modifying a large existing framework.

If you have any better ideas or interest and question in implementing in your own tool, pls leave a comment below.

Regexp application in bgp as-path attribute

The AS_PATH attribute is primarily used to prevent routing loops from an AS perspective and keep a record of all ASes traversed. Additionally, the path information can also be used in our BGP filtering policies, which we are gonna explore in this post.

1. Understanding AS_PATH

As RFC 4271 states :

AS_PATH is a well-known mandatory attribute.  This attribute
identifies the autonomous systems through which routing information
carried in this UPDATE message has passed.  The components of this
list can be AS_SETs or AS_SEQUENCEs.

And the modification of AS_PATH complies to the following rules :

When a BGP speaker propagates a route it learned from another BGP
speaker's UPDATE message, it modifies the route's AS_PATH attribute
based on the location of the BGP speaker to which the route will be
sent:

  a) When a given BGP speaker advertises the route to an internal
     peer, the advertising speaker SHALL NOT modify the AS_PATH
     attribute associated with the route.

  b) When a given BGP speaker advertises the route to an external
     peer, the advertising speaker updates the AS_PATH attribute as
     follows:
     1) if the first path segment of the AS_PATH is of type
        AS_SEQUENCE, the local system prepends its own AS number as
        the last element of the sequence (put it in the leftmost
        position with respect to the position of octets in the
        protocol message).  If the act of prepending will cause an
        overflow in the AS_PATH segment (i.e., more than 255 ASes),
        it SHOULD prepend a new segment of type AS_SEQUENCE and
        prepend its own AS number to this new segment.

     2) if the first path segment of the AS_PATH is of type AS_SET,
        the local system prepends a new path segment of type
        AS_SEQUENCE to the AS_PATH, including its own AS number in
        that segment.

     3) if the AS_PATH is empty, the local system creates a path
        segment of type AS_SEQUENCE, places its own AS into that
        segment, and places that segment into the AS_PATH.
When a BGP speaker originates a route then:

  a) the originating speaker includes its own AS number in a path
     segment, of type AS_SEQUENCE, in the AS_PATH attribute of all
     UPDATE messages sent to an external peer.  In this case, the AS
     number of the originating speaker's autonomous system will be
     the only entry the path segment, and this path segment will be
     the only segment in the AS_PATH attribute.

  b) the originating speaker includes an empty AS_PATH attribute in
     all UPDATE messages sent to internal peers.  (An empty AS_PATH
     attribute is one whose length field contains the value zero).

Whenever the modification of the AS_PATH attribute calls for
including or prepending the AS number of the local system, the local
system MAY include/prepend more than one instance of its own AS
number in the AS_PATH attribute.  This is controlled via local
configuration.

2. Matching On Cisco Routers

The Cisco Documentation Site lists the regular expression syntax for IOS in the Terminal Service Configuration Guide, it’s a small set of the *nix regular expression with little variation and therefore quite easy to use.

http://www.cisco.com/en/US/docs/ios/termserv/configuration/guide/tsv_reg_express_ps11746_TSD_Products_Configuration_Guide_Chapter.html

To make it more handy and easy to reference , the following PDF file from Packet Clearing House demonstrates some most commonly used expressions on cisco routers and can be used as a cheat sheet when composing them.

https://frankcui24.files.wordpress.com/2012/11/as-path.pdf

Applying the as_path policy on cisco router takes 2 steps :

  • The definition of as_path access-list and association with the route-map
  • Applying the route-map to neighbor and possibly doing a soft reconfig for inbound and outbound updates.

An example can be given as the following

! denying all NLRI information with private as range in as_path

ip as-path access-list 10 deny _[64512-65535]_
ip as-path access-list 10 permit .*

route-map BB1_IN permit 10
 match as-path 10

router bgp 123
 neighbor 200.200.12.1 route-map in

Before applying the as_path policy on the router, we should first verify the as_path regexp as following :

show ip bgp regexp _[64512-65535]_

3. Matching On Junos Routers

The regex engine on Junos routers tends to be closer to the *nix regex, and makes it easier for us to write more complex expressions.

The following two links list the regex configuration and verification commands respectively.

Configuration : http://www.juniper.net/techpubs/software/junos/junos94/swconfig-policy/defining-as-path-regular-expressions.html
Verification  : https://www.juniper.net/techpubs/en_US/junose12.0/information-products/topic-collections/command-reference-n-z/index.html?topic-17143.html