routingtable.java

使用Java语言编写模拟路由器程序

/* File: RoutingTable.java
 *
 * This file contains the code for the class RoutingTable,
 * that represents the routing table maintained by each 
 * router in the network
 */

import java.util.*;

/*
 * HashMap is a utility class provided by Java, which contains a hash table
 * implementation of the Map Interface. RoutingTable extends HashMap
 * 
 * Each entry in RoutingTable for router X is of the form (A,b) where, A: the id
 * of the destination router b: the HashMap containing the distances to A
 * through each neighbor of X. i.e.
 * 
 * Each entry in 'b' is of the form (C,d) where, C: a neighbor of X d: the
 * distance to A from X when the first hop is C
 * 
 * The RoutingTable is represented as a two-dimensional matrix in which -there
 * is a row for each destination in the network -there is a column for each
 * neighbor -an entry (x,y) represents the distance to node 'x' when the first
 * hop on the path is neighbor 'y'
 */
class RoutingTable extends HashMap {
	// the ID of the router to which this routing table belongs
	int routerId;

	// the outgoing neighbors of this router (the neighbors that will be present
	// in the routing table)
	HashSet neighbors;

	// the incoming neighbors of this router (the neighbors to which the
	// Distance Vectors must be sent)
	HashSet inNeighbors;

	/**
	 * Constructor
	 * 
	 * @routerId: the ID of the router to which the routing table belongs
	 * @topologyfile: the initial Topoloy Cofiguration File
	 * 
	 * Use: to construct the initial routing table for node 'routerId' from the
	 * initial topology
	 */
	public RoutingTable(int routerId, String topologyfile) {
		this.routerId = routerId;
		neighbors = new HashSet();
		inNeighbors = new HashSet();

		// initialize the toplogy
		Topology t = new Topology(topologyfile);
		LinkedList entries = t.getEntries();

		Iterator i = entries.iterator();

		// for each entry in the Topology Configuration File
		while (i.hasNext()) {
			TopologyFileEntry tfe = (TopologyFileEntry) i.next();

			// if it is and outgoing edge
			if (tfe.getRouter1() == routerId) {
				// add the other end to the list of outgoing neighbors
				updateWeight(tfe.getRouter2(), tfe.getWeight());
			}

			// if it is an incomin edge
			if (tfe.getRouter2() == routerId) {
				// add the other end to the list of incoming neighbors
				inNeighbors.add(new Integer(tfe.getRouter1()));
			}
		}
	}

	/*
	 * Method Name: updateWeight
	 * 
	 * @id: the id of the neighbor @weight: new weight
	 * 
	 * Use: To update the routing table when the weight of the link between this
	 * router and the neighbor changes
	 */
	synchronized boolean updateWeight(int id, int weight) {
		Integer ID = new Integer(id);

		// if the node is already not present in the routing table,
		// it means that it is a newly added neighbor
		//
		// so add a row to the routing table : all cols 10000 (inf)
		// add a column to the routing table : all rows 10000 (inf)
		// the intersection of the newly added row and column is the weight of
		// the link
		if (!containsKey(ID)) {
			// if COMMAND is trying to add a node that has weight inf, just
			// ignore it
			if (weight == 10000)
				return true;

			// create a new row
			HashMap h = new HashMap();

			// add an entry corresponding to each neighbor
			Iterator i = neighbors.iterator();

			while (i.hasNext()) {
				// make the distance as inf
				h.put(i.next(), new Integer(10000));
			}

			put(ID, h);

			// add the node to the list of neighbors
			neighbors.add(ID);

			// add a new column to the table
			i = entrySet().iterator();

			while (i.hasNext()) {
				((HashMap) (((Map.Entry) i.next()).getValue())).put(ID,
						new Integer(10000));
			}

			// the intersection of the new row and new column is the weight of
			// the new link
			h = (HashMap) get(ID);
			h.put(ID, new Integer(weight));
		}

		// if the node is present in the routing table
		// and if it is a neighbor, modify the column
		else if (neighbors.contains(ID)) {
			// if the link is deleted, delete the column
			if (weight == 10000) {
				Iterator i = entrySet().iterator();

				while (i.hasNext()) {
					((HashMap) (((Map.Entry) i.next()).getValue())).remove(ID);
				}

				// remove the node from the list of neighbors
				neighbors.remove(ID);
			}

			// else modify the column
			else {
				int change = weight
						- ((Integer) (((HashMap) get(ID)).get(ID))).intValue();

				Iterator i = entrySet().iterator();

				while (i.hasNext()) {
					HashMap h = (HashMap) ((Map.Entry) i.next()).getValue();

					int w = ((Integer) h.get(ID)).intValue();

					if (w == 10000) {
						// if the current distance to the destination is inf, it
						// would not change
					}

					else {
						h.put(ID, new Integer(w + change));
					}
				}
			}

		}

		// if the node is not a neighbor, add it to the neighbor's list
		else {
			if (weight == 10000)
				return true;

			// add the node to the list of neighbors
			neighbors.add(ID);

			Iterator i = entrySet().iterator();

			// create a column corresponding to the new neighbor
			while (i.hasNext()) {
				((HashMap) ((Map.Entry) i.next()).getValue()).put(ID,
						new Integer(10000));
			}

			HashMap h = (HashMap) get(ID);
			h.put(ID, new Integer(weight));
		}

		return true;
	}

	/*
	 * Method Name: deleteNode
	 * 
	 * @id: the id of the node
	 * 
	 * Use: To update the routing table when a neighbor is deleted
	 */
	synchronized boolean deleteNode(int id) {
		Integer ID = new Integer(id);

		// if the node is a neighbor, remove the corresponding row and column
		if (neighbors.contains(ID)) {
			Iterator i = entrySet().iterator();

			while (i.hasNext()) {
				((HashMap) (((Map.Entry) i.next()).getValue())).remove(ID);
			}

			neighbors.remove(ID);
			remove(ID);

			return true;
		}

		// if it is some other node in the network, ignore the message
		else if (containsKey(ID)) {
			return true;
		}

		// trying to delete an unidentified router
		return false;
	}

	/*
	 * Method Name: updateTable
	 * 
	 * @newdv: the Distance Vector @routerId: the id of the router that sent the
	 * Distance Vector ` Use: To update the routing table when a Distance Vector
	 * is received from a neighbor
	 */
	synchronized boolean updateTable(HashMap newdv, int routerId) {
		Integer ID = new Integer(routerId);

		// if the router that sent the distance vector is not a neighbor
		if (neighbors.contains(ID) == false) {
			return false;
		}

		// for each destination in the received distance vector newdv
		Iterator i = newdv.entrySet().iterator();

		while (i.hasNext()) {
			Map.Entry m = (Map.Entry) i.next();

			// the destination
			Integer node = (Integer) m.getKey();

			// the distance to the destination from the neighbor
			Integer weight = (Integer) m.getValue();

			// the distance to the neighbor
			Integer weightToNeighbor = (Integer) ((HashMap) get(ID)).get(ID);

			// if the destination is already present in table, modify the
			// distance to it under the neighbor's column
			if (containsKey(node)) {
				HashMap h = (HashMap) get(node);

				if (weight.intValue() != 10000) {
					h.put(ID, new Integer(weightToNeighbor.intValue()
							+ weight.intValue()));
				} else {
					// inf + sth = inf
					h.put(ID, new Integer(weight.intValue()));
				}
			}

			// if the destination is not present in the table, add it to the
			// table
			else {
				if ((node.intValue() == this.routerId)
						|| (weight.intValue() == 10000))
					continue;

				// create a new row
				HashMap h = new HashMap();

				Iterator j = neighbors.iterator();

				// make all the columns inf
				while (j.hasNext()) {
					h.put(j.next(), new Integer(10000));
				}

				// update the distance to this destination from the neighbor
				h.put(ID, new Integer(weightToNeighbor.intValue()
						+ weight.intValue()));

				put(node, h);
			}
		}

		i = entrySet().iterator();

		// for the destination that are not present in newdv but are present in
		// the table and not neighbors,
		// make the distance to the destination through that neighbor infinity

		while (i.hasNext()) {
			Map.Entry m = (Map.Entry) i.next();

			Integer node = (Integer) m.getKey();

			if ((newdv.containsKey(node) == false)
					&& (neighbors.contains(node) == false)) {
				if (node.intValue() == routerId)
					continue;
				((HashMap) m.getValue()).put(ID, new Integer(10000));
			}
		}

		HashMap h = getDistanceVector();

		i = h.entrySet().iterator();

		// if the min distance to a destination is infinity, delete that
		// destination from the table
		while (i.hasNext()) {
			Map.Entry m = (Map.Entry) i.next();

			if (((Integer) m.getValue()).intValue() == 10000) {
				remove(m.getKey());
			}
		}

		return true;
	}

	/**
	 * Method Name: getDistanceVector<p>
	 * 
	 * Use: To get the current Distance Vector
	 */

	synchronized HashMap getDistanceVector() {
		HashMap dv = new HashMap();

		Iterator i = entrySet().iterator();

		// for each destination
		while (i.hasNext()) {
			Map.Entry m = (Map.Entry) i.next();

			HashMap h = (HashMap) m.getValue();

			Iterator j = h.entrySet().iterator();

			int min = 10000;

			// for each neighbor
			while (j.hasNext()) {
				int v = ((Integer) (((Map.Entry) j.next()).getValue()))
						.intValue();

				// update the minimum distance to the destination
				if (v < min) {
					min = v;
				}
			}

			// add an entry (destination,distance) in the Distance Vector
			dv.put(m.getKey(), new Integer(min));
		}

		return dv;
	}

	/*
	 * Method Name: getNextHop
	 * 
	 * @ID: the id of the destination @distance: the current minimum distance to
	 * the destination
	 * 
	 * Use: To find the next hop to the destination, when the minimum distance
	 * to the destination is known
	 */
	synchronized String getNextHop(Integer ID, Integer distance) {
		HashMap h = (HashMap) get(ID);

		Iterator i = h.entrySet().iterator();

		while (i.hasNext()) {
			Map.Entry m = (Map.Entry) i.next();

			if (m.getValue().equals(distance)) {
				return m.getKey().toString();
			}
		}

		return "inf";
	}

	/*
	 * Method Name: getNeighbors
	 * 
	 * Use: To get the list of outgoing neighbors
	 */
	synchronized HashSet getNeighbors() {
		return neighbors;
	}

	/**
	 * Method Name: getInNeighbors<p>
	 * 
	 * Use: To get the list of incoming neighbors
	 */
	HashSet getInNeighbors() {
		return inNeighbors;
	}

	/*
	 * Method Name: getPaddedNumber
	 * 
	 * @n: the textual representation of a number
	 * 
	 * Use: To represent the number in 5 spaces for aligning the textual
	 * representation of the routing table
	 */
	String getPaddedNumber(String n) {
		if (n.equals("10000"))
			return " inf ";

		switch (n.length()) {
		case 1:
			return "  " + n + "  ";
		case 2:
			return "  " + n + " ";
		case 3:
			return " " + n + " ";
		case 4:
			return n + " ";
		default:
			return n;
		}
	}

	/*
	 * Method Name: toString
	 * 
	 * Use: To get a textual representation of the routing table
	 */
	synchronized public String toString_bak() {
		String result = "";
		Iterator i, j;

		result += getPaddedNumber("" + routerId);
		result += "|";

		i = neighbors.iterator();

		while (i.hasNext()) {
			result += getPaddedNumber("" + i.next());
		}

		result += "\n";

		for (int k = 0; k < ((neighbors.size() + 1) * 5 + 1); k++)
			result += "-";

		result += "\n";

		i = entrySet().iterator();

		while (i.hasNext()) {
			Map.Entry m = (Map.Entry) i.next();
			Integer ID = (Integer) m.getKey();
			HashMap h = (HashMap) m.getValue();

			result += getPaddedNumber("" + ID);
			result += "|";

			j = neighbors.iterator();

			while (j.hasNext()) {
				result += getPaddedNumber("" + h.get(j.next()));
			}

			result += "\n";
		}

		return result;
	}
	synchronized public String toString() {
		String result = "";
		Iterator i, j;

		

		i = neighbors.iterator();

		while (i.hasNext()) {
			//result += getPaddedNumber("" + i.next());
			Integer node = (Integer)i.next();
			result = "- ";
			result += getPaddedNumber("("+node+")");
			
			
			result += " -> Node (Port "+node+") \n";
		}
//		i = entrySet().iterator();

		return result;
	}

}