k_minima in Python

I am really excited about the Real World Haskell book that is coming out soon. I went through the slides from Bryan O'Sullivan's presentation. He describes implementing k_minima in Haskell. I wanted to give a go at implementing his Haskellish k_minima in Python using itertools. Here is what I came up with.

#! /usr/bin/env python

from itertools import *

DEBUG = False

def debug(*msgs):
    if DEBUG: print 'DEBUG:', msgs

def take(k, elements):
    """
    Extracts the first k elements from a list
    """
    if k > 0:
        for index, element in izip(count(), elements):
            debug('take', index, element)
            yield element
            if index == k - 1: break

def sort(elements):
    """
    Sorts a list
    """
    remaining = elements[:]
    while remaining:
        minimum = min(remaining)
        remaining.remove(minimum)
        debug('sort', minimum, remaining)
        yield minimum

def k_minima(k, elements):
    """
    Find the k least elements in a list
    """
    for element in take(k, sort(elements)):
        yield element

def main(k, elements):
    debug('main', k, elements)
    print list(k_minima(k, elements))

if __name__ == '__main__':
    import sys
    if len(sys.argv) > 2:
        elements = [int(arg) for arg in sys.argv[1:]]
        main(elements[0], elements[1:])
    else:
        print 'Useage: k_minima.py k element [element] ...'

Here is an example of running the program.

py$ ./k_minima.py 12 42 37 42 11 599 33 499 44 499 488 499 499 488347 448 4 588 7 85 48 59 84 
[4, 7, 11, 33, 37, 42, 42, 44, 48, 59, 84, 85]
py$ 

Getting the CAM table from Catalyst Switches using SNMP

Cisco has an article that describes a method for getting the CAM table (aka MAC address forwarding table) for Cisco Catalyst switches using SNMP. I developed a Python implementation of the procedure described in the article. My implementation uses the Zenoss pynetsnmp library. You can get the latest version of pynetsnmp from the Zenoss subversion repository at http://dev.zenoss.com/svn/trunk/pynetsnmp. The script also depends on the Twisted framework.

Here is the code

#! /usr/bin/env python

# http://www.cisco.com/en/US/tech/tk648/tk362/technologies_tech_note09186a0080094a9b.shtml

from pynetsnmp.tableretriever import TableRetriever
from pynetsnmp.twistedsnmp import AgentProxy
from twisted.internet import reactor
from pprint import pprint
import sys
import binascii
import logging

# oids
vtpVlanState = '.1.3.6.1.4.1.9.9.46.1.3.1.1.2'
dot1dBasePortIfIndex = '.1.3.6.1.2.1.17.1.4.1.2'
ifName = '.1.3.6.1.2.1.31.1.1.1.1'
dot1dTpFdbAddress = '.1.3.6.1.2.1.17.4.3.1.1'
dot1dTpFdbPort = '.1.3.6.1.2.1.17.4.3.1.2'

deffered_count = [0]
bridgeport_ifname = {}
vlan_ifname_mac = {}

def error(msg, proxy):
    print 'Error: %s' % msg
    proxy.close()
    reactor.stop()

def proc_fdb(result, proxy, vlan):
    fdbport_dct = {}
    for fdbport_key, fdbport_value in result[dot1dTpFdbPort].items():
        # .1.3.6.1.2.1.17.4.3.1.2.0.208.211.106.71.251 = INTEGER: 113
        fdb_key = fdbport_key.replace(dot1dTpFdbPort, '', 1)
        fdbport_dct[fdb_key] = int(fdbport_value)
    ifname_mac = {}
    for fdbaddress_key, fdbaddress_value in result[dot1dTpFdbAddress].items():
        # .1.3.6.1.2.1.17.4.3.1.1.0.208.211.106.71.251 = 
        #                                        Hex-STRING: 00 D0 D3 6A 47 FB
        fdbport_key = fdbaddress_key.replace(dot1dTpFdbAddress, '', 1)
        bridgeport = fdbport_dct[fdbport_key]
        if bridgeport_ifname.has_key(bridgeport):
            ifname = bridgeport_ifname[bridgeport]
            if not ifname_mac.has_key(ifname): ifname_mac[ifname] = []
            ifname_mac[ifname].append(binascii.hexlify(fdbaddress_value))
        else:
            logging.debug('no ifname for bridgeport=%s' % bridgeport)
    vlan_ifname_mac[vlan] = ifname_mac
    proxy.close()
    deffered_count[0] -= 1
    if not deffered_count[0]: 
        reactor.stop()
        pprint(vlan_ifname_mac)

def proc_vtpVlanState(result, proxy, create_proxy):
    proxy.close()
    ifindex_bridgeport = {}
    for oid, ifindex in result[dot1dBasePortIfIndex].items():
        ifindex_bridgeport[ifindex] = int(oid.split('.')[-1])
    for oid, ifname in result[ifName].items():
        ifindex = int(oid.split('.')[-1])
        if ifindex_bridgeport.has_key(ifindex):
            bridgeport_ifname[ifindex_bridgeport[ifindex]] = (ifindex, ifname)
        else:
            logging.debug('no bridge port for ifindex=%s' % ifindex)
    def vlans():
        for key in result[vtpVlanState].keys():
            vlan = int(key.split('.')[-1])
            if vlan < 1000: yield vlan
    for vlan in vlans():
        deffered_count[0] += 1
        vlan_proxy = create_proxy(vlan)
        vlan_proxy.open()
        d = TableRetriever(vlan_proxy, [dot1dTpFdbAddress, dot1dTpFdbPort])()
        d.addCallback(proc_fdb, vlan_proxy, vlan)
        d.addErrback(error, vlan_proxy)

def main(create_proxy):
    proxy = create_proxy()
    proxy.open()
    d = TableRetriever(proxy, [vtpVlanState, dot1dBasePortIfIndex, ifName])()
    d.addCallback(proc_vtpVlanState, proxy, create_proxy)
    d.addErrback(error, proxy)
    reactor.run()

if __name__=='__main__':
    if len(sys.argv) != 4:
        print 'Useage: main.py hostname version community'
    else:
        hostname, version, community = sys.argv[1:]
        def create_proxy(community_index=None):
            if community_index:
                _community = community + '@%s' % community_index
            else:
                _community = community
            return AgentProxy(hostname, 
                              snmpVersion=version, 
                              community=_community)
        main(create_proxy)

Here is an example of the output. You can see the VLAN number, the ifIndex, the interface name, and the list of MAC addresses associated with each interface.

$ ./main.py switch1 2c public
{1: {(10125, 'Gi0/25'): ['0016cbaebd91'],
     (10127, 'Gi0/27'): ['0015c55fc0e1'],
     (10128, 'Gi0/28'): ['00e08602ef22'],
     (10129, 'Gi0/29'): ['0013723bdd0d'],
     (10130, 'Gi0/30'): ['0050568a2f5d',
                         '005056a908ab',
                         '0050564936d4',
                         '005056a9543f',
                         '0050568a104d',
                         '000c297d74aa',
                         '0050568a51b3',
                         '005056ab2cff',
                         '0050568a7804',
                         '005056ab3e2e'],
     (10132, 'Gi0/32'): ['0016359fcba1'],
     (10133, 'Gi0/33'): ['0050568a0e85',
                         '0050568a7dfb',
                         '0050568a5553',
                         '0050568a1fb2',
                         '0050568a1cfb',
                         '0050568a79c2',
                         '0050568a58f9',
                         '00505642a408',
                         '0050568a7595'],
     (10134, 'Gi0/34'): ['0050568a59cc',
                         '0050568a5afb',
                         '0050568a5afe',
                         '0050568a1996',
                         '0050568a623e',
                         '0050568a5e9c',
                         '005056ab463d',
                         '0050568a68a6',
                         '0050568a2086',
                         '0050568a5269',
                         '0050568a5899',
                         '0050568a0558',
                         '0050568a2bb3',
                         '0050568a4f2e',
                         '0050564a7903',
                         '0050568a721d',
                         '0050568a2937',
                         '0050568a6bbe',
                         '0050568a5a49',
                         '0050568a259b',
                         '0050568a5ab2',
                         '0050568a68d0',
                         '005056ab34a8',
                         '0050568a1cd3'],
     (10135, 'Gi0/35'): ['0050568a269a',
                         '0050568a5662',
                         '005056ab0b11',
                         '0050568a0647',
                         '0050568a4454',
                         '005056ab0635',
                         '0050568a7b13',
                         '0050568a5b15',
                         '005056ab6513',
                         '0050568a44ac',
                         '0050564ee608'],
     (10136, 'Gi0/36'): ['0015c5f55b24'],
     (10137, 'Gi0/37'): ['005056ab0a52',
                         '005056ab6673',
                         '005056446cac',
                         '0050568a627c',
                         '0050568a54c6',
                         '0050568a2831',
                         '0050568a67c2'],
     (10138, 'Gi0/38'): ['0003ba1340ad'],
     (10139, 'Gi0/39'): ['000c298e5c1b', '000c2981b3cb', '0015c5e0b865'],
     (10140, 'Gi0/40'): ['005056ab7c2e',
                         '005056ab2f3b',
                         '0050568a1815',
                         '005056ab74a6',
                         '005056ab20be',
                         '0050564a6368',
                         '005056ab0bd3',
                         '005056a916cc',
                         '005056a97caa',
                         '005056ab7f68',
                         '005056ab51ac',
                         '005056ab4b36',
                         '005056ab6560',
                         '005056a94f6a',
                         '0050568a5b4a',
                         '005056ab2821',
                         '005056ab3ca6'],
     (10141, 'Gi0/41'): ['00304899fa5c'],
     (10145, 'Gi0/45'): ['001f12258106'],
     (10147, 'Gi0/47'): ['0050568a3d37',
                         '0050568a7ead',
                         '0050568a4b2e',
                         '005056ab2fdc',
                         '005056ab632a',
                         '005056a9018b',
                         '0050568a42a0',
                         '005056ab3d3b',
                         '00505645ff39',
                         '0050568a52ce',
                         '0050568a55d8',
                         '005056ab4898',
                         '005056a96d0b',
                         '0050568a00b6',
                         '0050568a4a18',
                         '0050568a4978',
                         '005056a9754c'],
     (10148, 'Gi0/48'): ['0019e70b4840', '0019e70b4802']},
 2: {},
 3: {},
 10: {}}

Zenoss

I am a software developer at Zenoss. We use Net-SNMP, RRDtool, and Python in our open-source network management product. From time to time, I come up with small snippets of code that might be useful to a large audience. I'll post those snippets here.