README 5.53 KB
Newer Older
1 2
Command Line Options
--------------------
3 4 5 6 7 8
This program reads from the standard input. Normally, only standard output is
written to. If there is an error, standard error is written to. Currently,
certain check results and progress messages are printed to standard error
as well. When the program is integrated with the rest of Emulab, these will
be removed.

9 10
For now, the command line should be
'ipassign -pc < <input_file> > <output_file>' for most uses.
11

12
Example: "bin/ipassign -c -p2 < graph/pastry44.graph"
13 14 15
         Use conservative bitspace allocation for 2 partitions with
         host-to-network routing on the pastry44 graph.

16
Example: "bin/ipassign -c -s < graph/smalltern.graph"
17 18 19 20 21 22 23
         Use conservative bitspace allocation for square root of the # of LANs
         partitions with host-host routing on the smalltern graph


'-p#'   When calculating assignment for ip addresses, # is used to set how
        many partitions to create. Example: '-p20' would create 20 partitions.

24 25 26 27 28
'-ps'   Search for the proper number of partitions by running METIS repeatedly
        and scoring the result.

'-pq'   Use the square root of the number of LANs as the number of partitions.
	(default)
29

30 31 32 33 34 35 36 37
'-pc'   Search for the proper number of partitions using METIS and scoring
        the result by ratio-cut.

'-pr'   Divide the graph in two with a ratio-cut


default Hierarchical bitspace allocation. Recursively partition the graph
        until the bitspace is used up.
38
'-c'    Use conservative bitspace allocation. Each level of the hierarchy
39
        is allocated a fixed number of bits.
40 41 42 43
#'-g'    Partition the graph using a greedy marriage algorithm instead of
#        METIS.
#        -- NOT IMPLEMENTED --

44 45
'-!'    Do not calculate routes or output them. Routes are no longer
        calculated here. Therefore this option does nothing.
46

Jonathon Duerig's avatar
Jonathon Duerig committed
47 48 49 50
Input
-----

The input consists of a series of specifications for LANs (a link is just a
51 52 53 54 55 56 57
LAN with only two nodes). Each LAN is specified by the number of bits used
to represent that LAN, number representing the weight (this must be integral), 
followed by a series of integers, each one representing a node which the LAN
is connected to. The LANs are automatically numbered in order of appearance
(starting at 0). Note that the number of bits is only used for dynamic IP
assignment, which is not yet implemented. Therefore the first number is
ignored for now.
Jonathon Duerig's avatar
Jonathon Duerig committed
58

59
<bits> <weight> <node> <node> [node [...]]
60 61 62

Example graph:

63 64 65 66 67 68 69
8 1 0 1
8 1 0 2
8 1 1 2

This graph would contain three LANs. The first has a weight of 1, and is
connected to nodes 0 and 1. The second is also of weight 1 and is
connected to nodes 0 and 2. The third is weight 1 and connects nodes 1 and 2.
70

71 72
Nodes should be numbered starting at 0 and every number up to (numNodes - 1)
should have an associated node.
Jonathon Duerig's avatar
Jonathon Duerig committed
73 74 75 76

Output
------

77 78 79 80
Output is divided into two sections. The first section associates each node-lan
connection pair with an IP address. The second section, delimited by '%%' on
a line by itself, shows the routing table associated with each node.

81
<ip-file> := <ip-line>*
Jonathon Duerig's avatar
Jonathon Duerig committed
82

83
<ip-line> := <LAN#> " " <node#> " " <IP-address> "\n"
Jonathon Duerig's avatar
Jonathon Duerig committed
84

85
An example of the output for the above graph would be:
86 87 88

0 0 10.0.0.1
0 1 10.0.0.2
89 90 91 92 93 94
1 0 10.0.1.1
1 2 10.0.1.2
2 1 10.0.2.1
2 2 10.0.2.2

If there was an error, this program returns 1, otherwise it returns 0.
95

Jonathon Duerig's avatar
Jonathon Duerig committed
96 97 98
Process
-------

99 100 101 102 103 104
Framework -- The framework processes the command line arguments and uses
             the results to figure out what kind of ip assignment and routing
             to do. Then it takes care of populating their inputs and acts
             as an intermediary for feeding the results of ip assignment
             into the router.

105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129
SquareRootPartition -- the square root of the number of LANs is calculated
    and this number is used to determine how many partitions METIS should
    create.

SearchPartition -- METIS is called repeatedly with different numbers of
    partitions and the result is scored. The best scored partitioning is then
    used. The scoring function optimizes for quickest routing speed by
    cubing the number of border LANs and adding the result to the sum of
    the cubes of each partition size.

FixedPartition -- METIS is used to create a specific number of partitions

ConservativeAssigner -- The largest LAN size is used to determine the number
    of bits used to represent hosts in a LAN. The largest partition size is
    used to determine the number of bits to represent LANs in a partition,
    and the remaining bits are used to represent partition number. This
    causes waste in bitspace usage, but the bitspace is large enough that this
    should only cause problems when tens or hundreds of thousands of nodes
    are in a network. If the largest LAN, the largest partition, and the number
    of partitions can each fit within their own 8-bitspace, then 8-bit
    boundaries are used because of human readability. Note that in addition
    to IP assignment, disconnected partitions are seperated here.

Exceptions
----------
Jonathon Duerig's avatar
Jonathon Duerig committed
130 131

Non-numeric and non-whitespace characters in the input are invalid.
132 133 134 135 136
Each LAN must have at least two nodes connected to it.
Input graphs should be connected.
Some graph configurations could cause the bitspace to be used up.
One of the input arguments may be invalid.
Various impossible conditions should never happen.
Jonathon Duerig's avatar
Jonathon Duerig committed
137 138 139 140

Room for Improvement
--------------------

141 142 143 144 145
Take the adaptive ip-assignment algorithm and turn it into an ip assignment
    module which works with the framework.
Change output format to be more compact. Possible change it to some form of
    binary representation.
Improve logging/testing automation.
Jonathon Duerig's avatar
Jonathon Duerig committed
146 147 148

Bugs
----