Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem I. 319. (April 2013)

I. 319. A few decades ago several network types existed, but nowadays almost all networks are based on TCP/IP. Devices are organized into subnetworks for more efficacy. Subnetworks can be created solely on a logical basis, however, they are generally also separated physically. Devices within the same network can communicate directly; other devices are accessed through the default gateway.

Every device in a TCP/IP network should have its IP address (that is, the device identifier), its netmask, the IP address of the default gateway (these last two items are properties of the subnetwork), finally, for an access by using domain names, the DNS server address. These addresses consist of four numbers, typically in a decimal format, separated by a period and each containing one byte of data.

The size of a subnetwork (that is, the number of corresponding IP addresses) can be determined from the netmask according to the following. There are some leading 1s in the binary form of the netmask, the remaining digits are then entirely 0s. Let k denote the number of 0s in the binary form of the netmask. The number of binary numbers having k binary digits, 2k, gives the corresponding number of addresses. Since the first address is the subnetwork address, and the last one is a special one (the ``broadcast address''), the total number of devices with distinct IP addresses in the subnetwork is 2k-2.

The subnetwork address and the broadcast address can be determined from the IP address of a device and from the corresponding netmask as follows. On one hand, the subnetwork address is formed by applying a logical AND operation to each binary digit pairs of the IP address and the netmask. On the other hand, the broadcast address is obtained if a bitwise logical OR operation is applied to the binary form of the IP address and the ones' complement of the netmask.

The file ipadat.txt (downloadable from our home page) contains data on some devices in the intranet of a certain company. Each line contains two pieces of data separated by one space character: the IP address and the netmask. The first few lines of the file is given below.

Your program should solve the following tasks. First, the number of the actual task (e.g., ``Task #6'') should be displayed. If the user is prompted for an input, a message describing the input should also appear (e.g., ``Give the number of employees''). Diacritical marks in the output may be omitted.

1. Read and store data from the file ipadat.txt in the appropriate format needed later.

2. Display on the screen the number of IP addresses in the file.

3. Create a function binbe. It should convert the successive (decimal) numbers in an IP address to adjacent blocks of 8-bit binary numbers as a text. For example, is converted to 00001010 00100000 00000000 00010001 (where space characters have been inserted here only for better readability).

4. Create your function binbol. It should convert a 32-digit binary number stored as text to the corresponding IP address in decimal form.

The following tasks can use the above functions directly, or through some other functions or procedures.

5. Read the value of a netmask in decimal form, then display on the screen the number of possible devices with different IP addresses within this network. (For example, the netmask corresponds to at most 4094 devices.)

6. In a certain institution subnetworks were created in such a way that their size is the smallest possible, but the number of devices with different IP addresses is at least 3 times the number of employees. Read the number of employees, then determine the decimal form of the netmask in the network.

7. Let us consider the company in the introduction above again. The last usable IP address of each subnetwork is assigned to the gateway. Display on the screen the line numbers in the file (separated by a space) that contain the subnetwork side IP address of such gateways.

8. Create a file csoport.txt containing the IP addresses of the ipadat.txt file grouped by subnetworks. The first line in each group should be the subnetwork address, then the corresponding addresses should be listed in each line (these lines containing an IP address should be indented with a tabulator character).

The output corresponding to the above input is shown below.

The source code (i319.pas, i319.cpp, ...) together with a short documentation (i319.txt, i319.pdf, ...) describing which developer environment to use for compiling should be submitted.

Downloadable file: ipadat.txt

(10 pont)

Deadline expired on May 10, 2013.

Sorry, the solution is available only in Hungarian. Google translation

A feladat megoldásai - még érettségi pontszámban kifejezve is - csak elenyésző mértékben tartalmaztak hibát. A beküldők sokféle megoldást adtak: volt, aki csak a kívánt függvényeket használta, míg mások kibővítették a függvények körét. A bővítés jó hatással volt az áttekinthetőségre és a kód hosszára.

Az értékelést az alábbi fájl alapján végeztük: i319ertekeles.pdf

A beküldött megoldások közül Tegzes Tamás gazdagon kommentezett munkáját választottuk. i319.pas


7 students sent a solution.
10 points:Csernák Tamás, Gema Barnabás, Qian Lívia, Tegzes Tamás, Varga 256 Erik.
9 points:Fényes Balázs, Németh 017 András.

Problems in Information Technology of KöMaL, April 2013