SSF.Net
Class TERoutingTable

java.lang.Object
  |
  +--SSF.Net.TERoutingTable

public class TERoutingTable

extends java.lang.Object

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

private TERoutingInfo	cache Single-line IP route cache.
private int	cache_dstip destination IP address of the route in the single-line route cache.
private int	cache_srcip source IP address of the route in the single-line route cache.
private int	ID The ID of the owning router.
private ProtocolGraph	inGraph The host for which this is the routing table.
private TERtgTblNode	root The root of this radix tree.
private boolean[]	route This boolean array and int are used only for printing purposes.
private boolean	SHOW_ADD Booleans indicate the different types of debugging messages and options, and whether or not they're enabled.
private TERouteTieBreaker	tieBreaker User-configurable tie breaker for choosing among same-cost routes.
static Net	topnet A reference to the top-level Net.
private TERtgTblNode	window A freely moving window for this tree.

Constructor Summary

TERoutingTable(TERouteTieBreaker T)
Constructs an empty routing table.

Method Summary

void	add(java.lang.String destination_ip, TEInterface via_nic, int next_hop_addr)
void	add(java.lang.String destination_ip, TEInterface via_nic, int next_hop_addr, double cost)
void	addDefault(TEInterface use_interface, int next_hop_addr)
void	addDefault(TEInterface use_interface, int next_hop_addr, double cost)
int	approxBytes() Returns an estimate of the number of bytes that would be produced by the conversion performed in toBytes.
private int	approxBytesHelper(int numbytes, TERtgTblNode x, int pos) Performs a pre-order traversal of this radix tree, calculating 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	del(java.lang.String destination)
TERoutingInfo	find(int ipAddr) Returns the data in the leaf of the path defined by the given boolean array, if the path exists.
TERoutingInfo	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.
TERoutingInfo	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).
TERoutingInfo	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, TERoutingInfo object) Inserts a boolean array into the tree.
private void	insertLeft() Inserts a RtgTblNode to the left child of the window.
private void	insertRight() Inserts a RtgTblNode to the right child of the window.
private int	ip2bytes(int plen, byte[] bytes, int bindex, boolean usenhi) Converts the IP address in the global route variable (applying the given prefix length to it) into a series of bytes and inserts them into a given byte array.
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.
private java.lang.String	preorderTraversal(java.lang.String str, java.lang.String indent, boolean usenhi, TERtgTblNode x, int pos) Performs a pre-order traversal of this radix tree and returns a string containing each IP address found along the way.
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)
void	remove(boolean[] bin) Removes the data at the node specified by the given boolean array.
private void	settopnet() Sets the reference to the top-level Net in the simulation.
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.
private int[]	toBytesHelper(byte[] bytes, int bindex, boolean usenhi, TERtgTblNode x, int pos, int entries) Performs a pre-order traversal of this radix tree, converting each node (forwarding table entry) into a series of bytes and inserting 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 java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

root

private TERtgTblNode root

The root of this radix tree.

window

private TERtgTblNode window

A freely moving window for this tree.

ID

private int ID

The ID of the owning router.

route

private boolean[] route

This boolean array and int are used only for printing purposes.

inGraph

private ProtocolGraph inGraph

The host for which this is the routing table.

SHOW_ADD

private boolean SHOW_ADD

Booleans indicate the different types of debugging messages and options, and whether or not they're enabled.

tieBreaker

private TERouteTieBreaker tieBreaker

User-configurable tie breaker for choosing among same-cost routes.

cache_dstip

private int cache_dstip

destination IP address of the route in the single-line route cache.

cache_srcip

private int cache_srcip

source IP address of the route in the single-line route cache.

cache

private TERoutingInfo cache

Single-line IP route cache.

topnet

public static Net topnet

A reference to the top-level Net.

Constructor Detail

TERoutingTable

public TERoutingTable(TERouteTieBreaker T)

Constructs an empty routing table.

Method Detail

getID

public int getID()

METHODS

add

public void add(java.lang.String destination_ip,
                TEInterface via_nic,
                int next_hop_addr)

add

public void add(java.lang.String destination_ip,
                TEInterface via_nic,
                int next_hop_addr,
                double cost)

addDefault

public void addDefault(TEInterface use_interface,
                       int next_hop_addr)

addDefault

public void addDefault(TEInterface use_interface,
                       int next_hop_addr,
                       double cost)

del

public void del(java.lang.String destination)

insertLeft

private void insertLeft()

Inserts a RtgTblNode to the left child of the window.

insertRight

private void insertRight()

Inserts a RtgTblNode to the right child of the window.

insert

public void insert(boolean[] bin,
                   TERoutingInfo object)

Inserts a boolean array into the tree. val is the return value of this existing path. val should not be -1. If the path is a network ID, then only the bits representing the network ID should be inserted. If the path is to a host, the full 32-bit should be inserted.

remove

public void remove(boolean[] bin)

Removes the data at the node specified by the given boolean array. If removing the data results in a subtree which contains no data at any node, that subtree is removed (snipped) from the tree.

find

public TERoutingInfo 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.

find

public TERoutingInfo 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.

findBest

public TERoutingInfo 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).

findBest

public TERoutingInfo 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).

settopnet

private void settopnet()

Sets the reference to the top-level Net in the simulation.

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

ip2bytes

private int ip2bytes(int plen,
                     byte[] bytes,
                     int bindex,
                     boolean usenhi)

Converts the IP address in the global route variable (applying the given prefix length to it) into a series of bytes and inserts them into a given byte array. NHI addressing can be used, though if there is no NHI equivalent, the byte encoding will be based on the standard dotted-quad IP address format. The first byte in the conversion indicates the notation of the encoding; 0 indicates dotted-quad, 1 indicates NHI. For the dotted-quad notation, the first byte is followed by five more bytes. There are four bytes, together comprising an int, which represents the value of the 32 bits in the IP address taken together as one number. This is followed by one byte for the prefix length. For the NHI notation, the first byte is followed by one byte which indicates whether or not the prefix length is 32 (in other words, whether or not it is an interface). This is necessary because otherwise certain addresses would have identical encodings. Following this, there is one byte which indicates the number separate IDs in the address. After that, there is one byte for each separate ID value (either network, host, or interface) of the address. For example, 1:3:1(4) has four IDs (netork 1, netork 3, host 1, interface 4).

Parameters:

plen - The prefix length to apply to route.

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 (if possible).

Returns:

the total number of bytes produced by 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

toBytesHelper

private int[] toBytesHelper(byte[] bytes,
                            int bindex,
                            boolean usenhi,
                            TERtgTblNode x,
                            int pos,
                            int entries)

Performs a pre-order traversal of this radix tree, converting each node (forwarding table entry) into a series of bytes and inserting 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.

x - The current table node.

pos - The bit position of the current IP prefix (tree depth).

entries - The number of entries in the table.

Returns:

an array containing (1) the total number of bytes used in the conversion and (2) the number of entries in the table

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

approxBytesHelper

private int approxBytesHelper(int numbytes,
                              TERtgTblNode x,
                              int pos)

Performs a pre-order traversal of this radix tree, calculating an estimate of the number of bytes that would be produced by the conversion performed in toBytes.

Parameters:

numbytes - The approximate number of bytes required so far.

x - The current table node.

pos - The bit position of the current IP prefix (tree depth).

Returns:

an estimate of the number of bytes produced by toBytes

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.

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.

preorderTraversal

private java.lang.String preorderTraversal(java.lang.String str,
                                           java.lang.String indent,
                                           boolean usenhi,
                                           TERtgTblNode x,
                                           int pos)

Performs a pre-order traversal of this radix tree and returns a string containing each IP address found along the way.

Parameters:

str - The table in string form, so far.

indent - A string to indent each line of the table with.

usenhi - Whether to print addresses in NHI or IP prefix format.

x - The current table node.

pos - The bit position of the current IP prefix (tree depth).

Returns:

the routing table as a string

push

public boolean push(ProtocolMessage message,
                    ProtocolSession fromSession)