The University of Western Ontario
Department of Computer Science

CS9668/4438 Internet Algorithmics

2018

Instructor

Roberto Solis-Oba
Office: MC 417
Email: solis@csd.uwo.ca

Lectures: Friday from 1:30 to 3:30 pm in MC105b
Office hours: Monday from 3:30 pm to 5:00 pm.
Course Description

Outline.

Assignments

Note. Please make it sure you use the latest version of the simulator, which again Daniel updated a few days ago.

Sample input files
    For question 4: input 1, input 2.

Algorithm to compute the finger tables from the configuration file. Sample input for this algorithm.
Simple algorithm to find a key in a peer-to-peer system. This algorithm does not use finger tables. Sample input for this algorithm.

Note. Please make it sure you use the latest version of the simulator, which Daniel updated a few days ago.
The name of your java class for question 1 must be Multicast.java and for question 2 it must be SumDist.java.

Sample input files
    For question 1: input 1, input 2, input 3, input 4, input 5, input 6.
    For question 2: input 2, input 3, input 3, input 4, input 5, input 6.

Here are some hints for question 1. Please do not read the hints until after you have tried to answer the question on your own.
Distributed algorithm to compute a breadth first search tree. Sample inputs for this algorithm input 1, input 2
Here are some hints for question 2.
Note. For this assignment you only need to consider line and ring networks with at least 2 processors and mesh networks with at least 2 rows and 2 columns.

Do try to design the algorithms for solving the questions in assignment 2 on your own. None of the exercises is intended to be very hard. If you are designing an overly complicated algorithm, you are probably doing something wrong. Any reasonable, correct algorithm is acceptable for any of the questions.

Here are some hints for question 1. Please do not read the hints until after you have tried to answer the question on your own.
Here are some hints for question 2.
Here are some hints for question 3.

Sample input files. For question 1: input 1. For question 2: input 2, input 3. For question 3: input 4, input 5, input 6. In each input file you will have to change the line with the LoadAlgorithm command by replacing the name of the java file with your own.
Network packets that you can use if you cannot use Wireshark: packet1, packet2, packet3

Lecture Notes

Available in OWL.
Teaching Assistants

TA Consulting times

Projects

Project due date: December 7

Topics

Organization of your report

Simulator for Synchronous Distributed Systems

You can download the simulator, documentation, and examples from this link.

Chat Server

cnaiapi library. Computer Networks and Internets API Library (Written by Michael H. Evangelista)
Cnaiapi library documentation
readln auxiliary library
cnaiapi.h
compile script
chat server
chat client

To compile the chat client and chat server, place all above files in the same directory, type

    compile chatclient

to compile the chat client and type

    compile chatserver

to compile the chat server. To run the server type

    chatserver portnumber

where portnumber is the port number that you want to use for the server. To run the client type

    chatclient serveraddress portnumber

where serveraddress is the symbolic address of the machine running the chat server, and portnumber is the port number selected by the chat server. The chat server must be started first.

      Chat server and chat client in Java
ChatClient.java
ChatServer.java

To compile the programs type

    java ChatClient.java ChatServer.java

To run the chat server type

    java ChatServer portnumber

To run the client type

    java ChatClient serveraddress portnumber

where serveraddress is the symbolic address of the machine running the chat server, and portnumber is the port number selected by the chat server. The chat server must be started first.

Marks

You can see your marks using OWL.
Paper describing the architecture of a web crawler

Paper describing PageRank
Paper about the structure of the Web Graph
Paper describing the greedy dual size algorithm -->