SSF.Net
Class RadixTreeRoutingTable

java.lang.Object
  |
  +--SSF.OS.ProtocolSession
        |
        +--SSF.Net.RadixTreeRoutingTable
All Implemented Interfaces:
com.renesys.raceway.DML.Configurable, RoutingTable

public class RadixTreeRoutingTable
extends ProtocolSession
implements RoutingTable

This class implements a radix-tree routing table. (Technically, it's a forwarding table. Unfortunately, we've been inconsistent with our terminology, often referring to forwarding tables as routing tables. Luckily (or not), many (or most) others in the networking world incorrectly refer to forwarding tables as routing tables. Proceed with care.)


Field Summary
static Net topnet
          A reference to the top-level Net.
 
Fields inherited from class SSF.OS.ProtocolSession
name, use
 
Constructor Summary
RadixTreeRoutingTable(ProtocolGraph forHost)
          Constructs an empty routing table.
RadixTreeRoutingTable(ProtocolGraph forHost, RouteTieBreaker T)
          Constructs an empty routing table.
 
Method Summary
 void add(java.lang.String destination_ip, NIC via_nic, int next_hop_addr)
          Add a route to the specified destination through the given interface.
 void add(java.lang.String destination_ip, NIC via_nic, int next_hop_addr, int cost)
          Add a route to the specified destination through the specified host with the given cost.
 void add(java.lang.String destination_ip, NIC via_nic, int next_hop_addr, int cost, java.lang.String routingProtocol)
          Add a route to the specified destination through the specified host with the given cost, from the given routing protocol (if any).
 void add(java.lang.String destination_ip, NIC via_nic, int next_hop_addr, java.lang.String routingProtocol)
          Add a route to the specified destination through the given interface from the given routing protocol (if any).
 void addDefault(NIC use_interface, int next_hop_addr)
          Add a default route through the specified host.
 void addDefault(NIC use_interface, int next_hop_addr, int cost)
          Add a default route through the specified host with the given cost.
 void addDefault(NIC use_interface, int next_hop_addr, int cost, java.lang.String protocol)
          Add a default route through the specified host with the given cost from the named routing protocol.
 void addFIBChangeListener(FIBChangeListener p)
          Register the given FIBChangeListener, so that it can be notified about changes to this FIB -- insertions or deletions of routes -- in order to make decisions about route redistribution.
 int approxBytes()
          Returns an estimate of the number of bytes that would be produced by the conversion performed in toBytes.
static int bytes2ip(java.lang.StringBuffer ip, byte[] bytes, int bindex)
          Converts a series of bytes to an IP address prefix as a string.
static int bytes2ipprefix(java.lang.StringBuffer ipp, byte[] bytes, int bindex)
          Converts a series of bytes to an IP address prefix in string format.
static int bytes2nhi(java.lang.StringBuffer nhi, byte[] bytes, int bindex)
          Converts a series of bytes to an NHI address.
static int bytes2str(java.lang.StringBuffer tbl, byte[] bytes, int bindex, java.lang.String ind, boolean usenhi)
          Converts a series of bytes to a forwarding table in string format.
 void clearTable()
          clear this routing table in case of changes in the ospf routing table.
 void config(com.renesys.raceway.DML.Configuration cfg)
          Configure this routing table by processing "route" and "nhi_route" attributes.
 void del(java.lang.String destination)
          Delete all routes to the destination.
 void del(java.lang.String destination, java.lang.String routingProtocol)
          Delete any routes to the destination that were originally inserted by the named routingProtocol.
 RoutingInfo find(int ipAddr)
          Returns the data in the leaf of the path defined by the given boolean array, if the path exists.
 RoutingInfo find(int ipAddr, int prefix_length)
          Returns the data in the leaf of the path defined by the given boolean array, if the path exists.
 RoutingInfo find(int ipAddr, int prefix_length, java.lang.String protocol)
          Returns the data in the leaf of the path defined by the given boolean array, if the path exists.
 RoutingInfo find(int ipAddr, java.lang.String protocol)
          Returns the first route inserted by the named protocol in the leaf of the path defined by the given boolean array, if the path exists.
 RoutingInfo findBest(int dstip)
          Returns the data in the node which is deepest in the tree along the path from the root to what would be the BEST (not EXACT) match in the tree, if it existed (which it might, in which case that would be the deepest node and thus the best match).
 RoutingInfo findBest(int srcip, int dstip)
          Returns the data in the node which is deepest in the tree along the path from the root to what would be the BEST (not EXACT) match in the tree, if it existed (which it might, in which case that would be the deepest node and thus the best match).
 int getID()
          METHODS
 void insert(boolean[] bin, RoutingInfo object)
          Inserts routing info into the table, keyed by the given binary string (boolean array), which represents an IP address prefix.
static int ipprefix2bytes(int val, int plen, byte[] bytes, int bindex)
          Converts an IP address prefix into a series of bytes and inserts them into a given byte array.
static int nhi2bytes(java.lang.String nhi, byte[] bytes, int bindex)
          Converts an NHI address into a series of bytes and inserts them into a given byte array.
 void print()
          Prints this radix tree.
 void print(java.lang.String indent)
          Prints this radix tree.
 void print(java.lang.String indent, boolean usenhi)
          Prints this radix tree.
 boolean push(ProtocolMessage message, ProtocolSession fromSession)
          Routine to call when a message is being sent to ("pushed into") this ProtocolSession by another ProtocolSession.
 void remove(boolean[] bin, java.lang.String source)
          Removes the data at the node specified by the given boolean array, and having the given source protocol.
 void removeFIBChangeListener(FIBChangeListener p)
          Unregister the given FIBChangeListener.
 void rep(java.lang.String destination_ip, NIC via_nic, int next_hop_addr, int cost, java.lang.String routingProtocol)
          Inserts new routing information into the table, replacing any previous routing information from the same routing protocol that may have already existed.
 void replace(boolean[] bin, RoutingInfo object, java.lang.String source)
          Inserts new routing information into the table, replacing any previous routing information from the same routing protocol that may have already existed.
 void setAdminDistance(java.lang.String protocolName, int distance)
           
 void setDefaultAdminDistances()
           
 int toBytes(byte[] bytes, int bindex, boolean usenhi)
          Converts this forwarding table into a series of bytes and inserts them into a given byte array.
 java.lang.String toString()
          Prints this radix tree to a string and returns it.
 java.lang.String toString(java.lang.String indent, boolean usenhi)
          Prints this radix tree to a string and returns it.
 
Methods inherited from class SSF.OS.ProtocolSession
close, closed, debugIdentifier, inGraph, init, open, opened, pushAfterDelay, pushAfterDelayFailed, setGraph, version
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

topnet

public static Net topnet
A reference to the top-level Net.

Constructor Detail

RadixTreeRoutingTable

public RadixTreeRoutingTable(ProtocolGraph forHost)
Constructs an empty routing table.


RadixTreeRoutingTable

public RadixTreeRoutingTable(ProtocolGraph forHost,
                             RouteTieBreaker T)
Constructs an empty routing table.

Method Detail

addFIBChangeListener

public void addFIBChangeListener(FIBChangeListener p)
Register the given FIBChangeListener, so that it can be notified about changes to this FIB -- insertions or deletions of routes -- in order to make decisions about route redistribution.

Specified by:
addFIBChangeListener in interface RoutingTable

removeFIBChangeListener

public void removeFIBChangeListener(FIBChangeListener p)
Unregister the given FIBChangeListener.

Specified by:
removeFIBChangeListener in interface RoutingTable

setAdminDistance

public void setAdminDistance(java.lang.String protocolName,
                             int distance)

setDefaultAdminDistances

public void setDefaultAdminDistances()

config

public void config(com.renesys.raceway.DML.Configuration cfg)
            throws com.renesys.raceway.DML.configException
Configure this routing table by processing "route" and "nhi_route" attributes. The two forms differ in their value syntax: "route" specifies IP addresses in "a.b.c.d/m" format, while "nhi_route" specifies NHI addresses in "net:..:net:host(interface)" format.

A route or nhi_route attribute must provide a relative NHI destination ("dest") plus an interface number ("interface"). If the specified interface is other than point-to-point, a next hop NHI address ("next_hop") must be supplied as well. Administrative distances for protocols default to the Cisco defaults, unless the user specifies otherwise within the optional "routing" configuration block for the host:

     host [ # ..
       routing [  # Value OSPF routes more highly than EBGP, etc. 
         administrative_distance [protocol OSPF value 10] 
         administrative_distance [protocol EBGP value 20] 
         administrative_distance [protocol RIP  value 30] 
      ]
    ]
 

Specified by:
config in interface com.renesys.raceway.DML.Configurable
Overrides:
config in class ProtocolSession
com.renesys.raceway.DML.configException

getID

public int getID()
METHODS


add

public void add(java.lang.String destination_ip,
                NIC via_nic,
                int next_hop_addr)
Description copied from interface: RoutingTable
Add a route to the specified destination through the given interface.

Specified by:
add in interface RoutingTable

add

public void add(java.lang.String destination_ip,
                NIC via_nic,
                int next_hop_addr,
                java.lang.String routingProtocol)
Description copied from interface: RoutingTable
Add a route to the specified destination through the given interface from the given routing protocol (if any).

Specified by:
add in interface RoutingTable

add

public void add(java.lang.String destination_ip,
                NIC via_nic,
                int next_hop_addr,
                int cost)
Description copied from interface: RoutingTable
Add a route to the specified destination through the specified host with the given cost.

Specified by:
add in interface RoutingTable

add

public void add(java.lang.String destination_ip,
                NIC via_nic,
                int next_hop_addr,
                int cost,
                java.lang.String routingProtocol)
Description copied from interface: RoutingTable
Add a route to the specified destination through the specified host with the given cost, from the given routing protocol (if any).

Specified by:
add in interface RoutingTable

addDefault

public void addDefault(NIC use_interface,
                       int next_hop_addr)
Description copied from interface: RoutingTable
Add a default route through the specified host.

Specified by:
addDefault in interface RoutingTable

addDefault

public void addDefault(NIC use_interface,
                       int next_hop_addr,
                       int cost)
Description copied from interface: RoutingTable
Add a default route through the specified host with the given cost.

Specified by:
addDefault in interface RoutingTable

addDefault

public void addDefault(NIC use_interface,
                       int next_hop_addr,
                       int cost,
                       java.lang.String protocol)
Description copied from interface: RoutingTable
Add a default route through the specified host with the given cost from the named routing protocol.

Specified by:
addDefault in interface RoutingTable

rep

public void rep(java.lang.String destination_ip,
                NIC via_nic,
                int next_hop_addr,
                int cost,
                java.lang.String routingProtocol)
Description copied from interface: RoutingTable
Inserts new routing information into the table, replacing any previous routing information from the same routing protocol that may have already existed.

Specified by:
rep in interface RoutingTable

del

public void del(java.lang.String destination)
Delete all routes to the destination.

Specified by:
del in interface RoutingTable

del

public void del(java.lang.String destination,
                java.lang.String routingProtocol)
Delete any routes to the destination that were originally inserted by the named routingProtocol. Special case: routingProtocol "*" deletes all routes.

Specified by:
del in interface RoutingTable

insert

public void insert(boolean[] bin,
                   RoutingInfo object)
Inserts routing info into the table, keyed by the given binary string (boolean array), which represents an IP address prefix. Any number of instances of routing information may co-exist at the same node, in linked list format. Once the node represented by the binary string is found, the following algorithm is applied to determine how the data at that node will be affected. (1) If there is no data at the node, the new data will be added, forming a linked list of size 1. (2) If there is already a linked list of data at the node, then insert the new data into the linked list, ensuring that the list remains sorted primarily by administrative distance, secondly by cost, and thirdly by insertion time.


replace

public void replace(boolean[] bin,
                    RoutingInfo object,
                    java.lang.String source)
Inserts new routing information into the table, replacing any previous routing information from the same routing protocol that may have already existed.


remove

public void remove(boolean[] bin,
                   java.lang.String source)
Removes the data at the node specified by the given boolean array, and having the given source protocol.


find

public RoutingInfo find(int ipAddr)
Returns the data in the leaf of the path defined by the given boolean array, if the path exists. Returns NULL if the path does not exist.

Specified by:
find in interface RoutingTable

find

public RoutingInfo find(int ipAddr,
                        java.lang.String protocol)
Returns the first route inserted by the named protocol in the leaf of the path defined by the given boolean array, if the path exists. Returns NULL if the path does not exist.


find

public RoutingInfo find(int ipAddr,
                        int prefix_length)
Returns the data in the leaf of the path defined by the given boolean array, if the path exists. Returns NULL if the path does not exist.

Specified by:
find in interface RoutingTable

find

public RoutingInfo find(int ipAddr,
                        int prefix_length,
                        java.lang.String protocol)
Returns the data in the leaf of the path defined by the given boolean array, if the path exists. Returns NULL if the path does not exist. If protocol is "*", return all data; otherwise, return the first datum that was inserted by the named protocol.


findBest

public RoutingInfo findBest(int dstip)
Returns the data in the node which is deepest in the tree along the path from the root to what would be the BEST (not EXACT) match in the tree, if it existed (which it might, in which case that would be the deepest node and thus the best match).

Specified by:
findBest in interface RoutingTable

findBest

public RoutingInfo findBest(int srcip,
                            int dstip)
Returns the data in the node which is deepest in the tree along the path from the root to what would be the BEST (not EXACT) match in the tree, if it existed (which it might, in which case that would be the deepest node and thus the best match).

Specified by:
findBest in interface RoutingTable

nhi2bytes

public static int nhi2bytes(java.lang.String nhi,
                            byte[] bytes,
                            int bindex)
Converts an NHI address into a series of bytes and inserts them into a given byte array.

Parameters:
nhi - A string containing the NHI address.
bytes - A byte array in which to place the results.
bindex - The index into the given byte array at which to begin placing the results.
Returns:
the total number of bytes produced by the conversion

bytes2nhi

public static int bytes2nhi(java.lang.StringBuffer nhi,
                            byte[] bytes,
                            int bindex)
Converts a series of bytes to an NHI address.

Parameters:
nhi - A StringBuffer into which the results will be placed. It must be initialized to the empty string.
bytes - The byte array to convert to an NHI address.
bindex - The index into the given byte array from which to begin converting.
Returns:
the total number of bytes used in the conversion

ipprefix2bytes

public static int ipprefix2bytes(int val,
                                 int plen,
                                 byte[] bytes,
                                 int bindex)
Converts an IP address prefix into a series of bytes and inserts them into a given byte array.

Parameters:
val - The integer value of the 32 bits of the IP address when taken as a whole.
plen - The prefix length.
bytes - A byte array in which to place the results.
bindex - The index into the given byte array at which to begin placing the results.
Returns:
the total number of bytes produced by the conversion

bytes2ipprefix

public static int bytes2ipprefix(java.lang.StringBuffer ipp,
                                 byte[] bytes,
                                 int bindex)
Converts a series of bytes to an IP address prefix in string format.

Parameters:
ipp - A StringBuffer into which the results will be placed. It must be initialized to the empty string.
bytes - The byte array to convert to an IP address prefix.
bindex - The index into the given byte array from which to begin converting.
Returns:
the total number of bytes used in the conversion

bytes2ip

public static int bytes2ip(java.lang.StringBuffer ip,
                           byte[] bytes,
                           int bindex)
Converts a series of bytes to an IP address prefix as a string. The notation of the prefix (either dotted-quad or NHI) must be specified by the first byte (0 indicates dotted-quad, 1 indicates NHI).

Parameters:
bytes - The byte array to convert to an IP address prefix.
bindex - The index into the given byte array from which to begin converting.
Returns:
the total number of bytes used in the conversion

toBytes

public int toBytes(byte[] bytes,
                   int bindex,
                   boolean usenhi)
Converts this forwarding table into a series of bytes and inserts them into a given byte array.

Parameters:
bytes - A byte array in which to place the results.
bindex - The index into the given byte array at which to begin placing the results.
usenhi - Whether or not to use NHI addressing.
Returns:
the total number of bytes produced by the conversion

approxBytes

public int approxBytes()
Returns an estimate of the number of bytes that would be produced by the conversion performed in toBytes. The estimate is the same whether or not NHI addressing is used.

Returns:
the total number of bytes produced by the conversion

bytes2str

public static int bytes2str(java.lang.StringBuffer tbl,
                            byte[] bytes,
                            int bindex,
                            java.lang.String ind,
                            boolean usenhi)
Converts a series of bytes to a forwarding table in string format.

Parameters:
tbl - A StringBuffer into which the results will be placed. It must be initialized to the empty string.
bytes - The byte array to convert to a forwarding table.
bindex - The index into the given byte array from which to begin converting.
ind - The string with which to indent each line.
usenhi - Whether or not to use NHI addressing.
Returns:
the total number of bytes used in the conversion

toString

public java.lang.String toString()
Prints this radix tree to a string and returns it.

Overrides:
toString in class java.lang.Object
Returns:
a string containing a printout of the tree

toString

public java.lang.String toString(java.lang.String indent,
                                 boolean usenhi)
Prints this radix tree to a string and returns it.

Parameters:
indent - A string to be used to prefix each output line.
usenhi - Whether to print addresses in NHI or IP prefix format.
Returns:
a string containing a printout of the tree

print

public void print()
Prints this radix tree. Data from each node goes on a separate line by itself.

Specified by:
print in interface RoutingTable

print

public void print(java.lang.String indent)
Prints this radix tree. Data from each node goes on a separate line by itself.

Parameters:
indent - A string to be used to prefix each output line.

print

public void print(java.lang.String indent,
                  boolean usenhi)
Prints this radix tree. Data from each node goes on a separate line by itself.

Parameters:
indent - A string to be used to prefix each output line.
usenhi - Whether to print addresses in NHI or IP prefix format.

push

public boolean push(ProtocolMessage message,
                    ProtocolSession fromSession)
Description copied from class: ProtocolSession
Routine to call when a message is being sent to ("pushed into") this ProtocolSession by another ProtocolSession. The pusher sends a reference to itself in the second argument. This push happens immediately, without any simulation time elapsing, regardless of other activities taking place in the ProtocolGraph.

If you desire "safe" interaction with other CPU activities, even though your push() consumes no measurable/modelable CPU cycles, define the "cpudelay true" attribute for the ProtocolGraph and use pushAfterDelay(message,fromSession,0.0). This will guarantee proper ordering; that is, the framework will wait until the CPU is free before proceeding with the requested push().

Specified by:
push in class ProtocolSession

clearTable

public void clearTable()
clear this routing table in case of changes in the ospf routing table. Used by OSPF to update this table correctly.