Programming Assignment 6 - Backbone Routing

See the assignment turn-in page for instructions on turning in your assignment.

Each network segment consists of one or more routers. Each router has a name of the form Ri where i is a sequence of one or more decimal digits; for example, R0001 and R3453333 are router names. Each router on a network segment has a name unique within that segment, but router names may be repeated among network segments; for example the router R0101 may appear in both the Terra Haute and Walla Walla subnets, but within each subnet there is only one router named R0101.

Every three days the ISP's nationwide network operations center gathers traffic statistics from each of its network segments and recomputes new routing tables based on the collected traffic statistics. The routing-table generator creates a single file named routing-tables consisting of zero or more records, where each record has the following format:

segment-name router-name router-table

• segment-name - a text field giving the name of the segment; this field may contain spaces, for example Kansas City.

• router-name - a text field giving the name of the router; the name has the format given above.

• router-table - A byte sequence giving the new routing table. The format of the byte sequence is

  d₁d₂b₁ . . . b_nd₁d₂

  where d_i are the delimiter bytes, b_i are the data bytes, and n > 0. The delimiter bytes are always different from the data bytes, so there can be no confusion as to which is which; the delimiter bytes are also guarenteed not to be white-space characters. Apart from being different from the delimiter bytes, each data byte may contain any value from 0 to 255, including white-space characters.

  Here is an example routing table:

  /\jfk39nd$NCL:@W+cjedy4*/\

  In this example the delimiter bytes are d₁ = '/' and d₂ = '\', the first data byte is 'j', the last data byte is '*', and n is 22.

  Note that routing tables contain bytes and not characters. This means routing tables contain non-printable values, and you will almost certainly screw up your terminal or printer if you attempt to print a file containing routing tables. You may be able to use your editor to look at the file, depending on your editor (emacs does alright on files containing routing tables).

Within a record, each field is separated from the other by a white-space character; any white-space character may be used (the white-space characters are space, tab, or newline).

Each record immediately follows the next; there are no white-space characters separating one record from another. Records appear in arbitrary order in the generated file.

router-name byte-count router-table

• router-name - a text field giving the name of router to which the table applies.

• byte-count - a text field giving the number of bytes in the router table.

• router-table - a sequence of data bytes making up a router table; the delimiter bytes do not appear in the router table.

A single space character ' ' separates one field from the next; no characters separate one record from the rest. Records in a network-segment file are stored in ascending order by router name; use the order operators defined for the string class to determine order.

The name of a network-segment file is based on the name of the network segment with the following changes:

• The network-segment filename is in all lower-case letters; for example the network-segment file for Trenton has the name trenton.

• Any space characters in the network-segment name are replaced by the hyphen character '-'; for example, the network-segment file for New Orleans has the name new-orleans

• The file ends with the .rt extension.

For example, the network segment San Francisco has san-francisco.rt as the name of its network-segment file.

from any PC lab machine running linux or rockhopper.