Create a gist now

Instantly share code, notes, and snippets.

@chase-smith /notes.asciidoc Secret
Last active Mar 8, 2017

What would you like to do?
CSC469/569 notes

CSC469/569 notes

Table of Contents
Another day of class

Week 1.1 - Jan 03

Class overview

Testing/assignment schedule

Week Type Percent
















Grad requirements

  • Pick a networking related topic

  • Investigate it

  • Write an 8-10 page paper

  • Do a presentation to the class, no more than 30 minutes in length

Computer Networks


Computer network

Collection of computing devices interconnected to enable data exchange

Graph model of computer network

V = set of vertices/nodes (computers)

E = set of edges — communication links

  / |
 /  |

Computing devices

  • Computers (PCs, mainframes, phones)

  • GPS

  • Embedded processors

    • Cars, fridges, etc

Examples of services provided by computer networks

  • Resource sharing

    • Printers, files, data

  • Online/electronic banking

  • Email

  • Instant messaging

  • Social networks

  • Voice over IP

  • Audio/video streaming

  • Gaming

  • Remote login

Classification of computer networks by size

LAN (Local Area Network)

1 or a few buildings

MAN (Metropolitan Area Network)

Network that covers something like a city

WAN (Wide Area Network)

Country/continent/entire planet

PAN (Personal Area Network)

Usually span a single room, a car, or a desktop. Usually use Bluetooth

Classification by Topology

Ring Topology

Each node is connected to the one next to it, in a ring

A -> B
^    |
|    v
D <- C

Star Topology

Central hub, each device connects only to the hub

    o   o
    |  /
    | /

Example: Ethernet

Mesh Topology

Nodes connect freely to each other

|     |
|     |
o---o |
 \  | |
  \ | |

Bus Topology

Data sent by one station is received by all stations on the same link. Stations who the message is not intended for drop the message.

        o       o        o
        |       |        |
            |       |
            o       o


An internet (or internetwork) is a collection of interconnected computer networks

To interconnect two networks N1, N2

N1                N2
+---------+       +---------+
|   o--o  |       |   o--o  |
|   |  |  |       |   |  |  |
|o--o  |  |       |   |  |  |
|   |  |  |       |   |  |  |
|   o--o  |       |   o--o  |
+---------+       +---------+


N1                N2
+---------+       +---------+
|   o--o  |-------|   o--o  |
|   |  |             /|  |  |
|o--o  |------o-----< |  |  |
|   |  |             \|  |  |
|   o--o  |-------|   o--o  |
+---------+       +---------+

You need a computer that is in both networks, called a packet switch

Different types of switches
  • Bridges

  • Link layer switches

  • Routers

2 types of nodes
  • End-systems

    • Also called hosts

    • Run end-user applications

  • Packet switches

    • Exist to interconnect computers

    • Do not run end-user software

Carry data (bits and bytes) encoded as electromagnetic signals

Electromagnetic spectrum

                 visible light
     radio waves      |                        infrared
          |           |                            |
      |------|     |-----|                   |-----------|
low wavelength                                        high wavelength
  • Guided media

    • Cables or wires

    • Physical medium guides the signals from source to destination

    • Examples

      • Twisted pair

        • Phone, ethernet

        • Carries signals encoded as electrical voltages

      • Coax cable

        • Cable TV systems

        • Carries signals encoded as electrical voltages

      • Optical fiber

        • Thin strands of glass

        • Use lasers to transmit data

          • Laser on ⇒ 1, laser off ⇒ 0

          • Have timeslots (frequency) to expect to receive/not receive a pulse

  • Unguided media

    • Radio and satellite signals

  • Point-to-point links

    • Dedicated link between two stations

    • Can only be used by those two stations

    • o-------o

    • Usually guided media

  • Broadcast link

    • Link is shared among a number of stations

    • Examples

      • Satellite signals

      • TV

      • Radio

    • See [Bus Topology](#bus-topology) section

Global Internet

ISPs have networks of packet switches

  ISP 1
   |       ISP 2
+------+    |    Home network
|   o  |  |---|    |
| o    x--| o x----x
|  o o |  |---|

Access Network

Access network for a computer C is the network through which C connects to the ISP’s network

Types of Access Networks
  • DSL (Digital Subscriber Line)

    • Telephone company

    • Twisted pair

  • Cable

    • Cable TV company

    • Coax

  • Dial up

    • Telephone company

    • Twisted pair

  • Fiber to the home (FTTH)

    • Optic fiber

  • Satellite


Phone lines were originally intended to carry voice, not data.

               Home network
                    |                                 Telephone company
+-------------------+------------------------+        central office
|                                            |                 +
|        Telephone                           |                 |
|           +         Splitter               |    +------------+-------------+
|           |            +                   |    |                          |
|           |            |                   |    |    +-----------+         |
|           +--------+---+--+--------------------------+           |         |
|                    |      |                |    |    |  DSLAM    |         |
|                    |      |                |    |    |           |         |
|                    +---+--+                |    |    +-----------+         |
|                        |                   |    |                          |
|              +---------+-+                 |    +--------------------------+
|              | DSL Modem |                 |
|              +----^------+                 |
|                   |                        |
|                   |                        |
|    Ethernet port  |                        |
|       +-----------+                        |
|       |                                    |
|       |                                    |
|       |                                    |
|       +--+Ethernet switch                  |
|              |   +    +                    |
|              |   |    |                    |
|              |   |    +--------->Device    |
|              |   |                         |
|              |   +---------->Device        |
|   Device<----+                             |
|                                            |
|                                            |

DSLAM * DSL Access Multiplexer

Phone lines can carry signals in the 0 to 1 MHz range. DSL divides this spectrum into 3 bands.
  • 0 - 4KHz

    • Voice signals

  • 4KHz - 50KHz

    • Upstream data channel

  • 50KHz - 1MHz

    • Downstream data channel

Another day of class

Week 1.2 - Jan 05

Dial up

Basically the same idea as DSL, using a phone line to transfer data, with limited bandwidth.


Cable Modem Termination System

Cable distribution diagram
                                                                      Cable company's head end (office)
                                                                   |                                  |
                                                                   |                    ISP's Router  |
    Spine of coax cable                                            |                                  |
                                                                   |                   +----------+   |
+--------------------------+                                       |    +---------+    |          |   |
                           |                      Optic fiber      |    |         |    |          |   |
                           |                  +-------------------------+         |    |          |   |
                           |                  |                    |    +---------+    |          |   |
                           |                  |                    |    CMTS           +----------+   |
                           |              +---+-+                  |                                  |
                           +--------------+     |                  +----------------------------------+
                                          |     |
                     |                     Fiber node
      |       |      | Coax - shared
      |       |      | broadcast medium
      +       +      +
    House   House  House

Inside a home, you have a unit from the cable company, a cable modem. Generally plugged into a router+WiFi access point. In order for data to leave, the modem transforms it into a format suitable for transmitting over cable. Once data reaches the fiber node, it is transformed again, as fiber has much more bandwidth than cable.

Cable internet is HFC - Hybrid Fiber Coax.

Packet Switching


When transmitting data across a link or an entire network, it is sent in blocks that are ultimately referred to as frames, packets, or cells (name changes depending on the context, ie what layer of the network you are talking about).

Each network technology has a minimum size for the transmission unit, as well as a maximum size.

Ethernet - minimum of 74 bytes, max ~1520 bytes.

Long messages are chopped up into a sequence of packets. Each packet has a

  • Payload (data to be transmitted)

  • Header

    • Sequence numbers

    • Addressing information

    • Error checking information

  • Optional trailer


| Header | Payload | Trailer |

Packet Switching

Each packet contains a source and a destination address, and is independently routed to its destination. It is possible that multiple packets, sent consecutively, will take different paths through the network and thus arrive out of order. This could be caused by network congestion or transmission errors (corrupted/missing packets). Packets can also be lost if, for example, a router receives packets faster than it can send them out and the buffer fills up; in this case, the router will end up dropping packets.

The Internet uses packet switching to deliver data.


You write a long message to someone, and put each page in its own envelope. You then take all of the envelopes to the post office.

Circuit Switching

Circuit switching is an alternative method of moving data through a network.

A message is chopped up into a sequence of cells. Then:

  1. There is a setup phase that sets up a "circuit" (ie sequence of routers from source to destination). This is called a virtual circuit

  2. Resources (buffer space in routers, link bandwidth) are reserved for the virtual circuit

  3. A virtual circuit identifier is assigned and stored in the headers of all cells of the message

  4. Send the cells

The result is that all of the cells all follow the same route, and all arrive in the same order.


More like a phone call. You dial someone up, and when you get a connection, you start talking. The phone company will figure out a way to route the call through the network.

Circuit switching reserves resources, while packet switching allocates resources on demand. Both packet switching and circuit switching use a forwarding table at each router.

2 ways to implement circuit switching (sharing link bandwidth)

  1. Frequency division multiplexing (FDM)

  2. Time division multiplexing (TDM)

FDM - Frequency Division Multiplexing

Divide up the bandwidth into channels (bands); multiple circuits can transmit data at the same time, they just have to use different bands.

TDM - Time Division Multiplexing

Time is divided into intervals of fixed size; each interval is divided into N equal sized time slots (assuming there are N virtual circuits).

Example N=3:

| 1 | 2 | 3 | 1 | 2 | 3 | 1 | 2 | 3 | ... |

Table 1. Packet Switching vs Circuit Switching
Feature Packet switching Circuit switching

Congestion (packets sent can be dropped)






Network Performance

Each link is characterized by a

  • Transmission rate

    • Number of bits/second that can be put onto the link

  • Propagation delay

    • How long it takes a bit to traverse the link

    • Depends on characteristics of the link, such as distance

Transmission delay

Amount of time it takes to transmit a packet.

L/R where L = number of bits in a packet and R = transmission rate of the link

Extra delays can be incurred when there are multiple links.

Routers can have multiple interfaces (links). A router has a queue (output buffer) for each link.

Store and forward

The entire packet must be received before it can be forwarded on an outgoing link

Once a packet has been received, the router must determine which link the packet needs to be sent out on. If the link is busy, the router must buffer the packet.

Delays experienced within a router:
  • Processing delay

    • Time the router takes to examine the packet header to determine outgoing interface

  • Queueing delay

    • Time the packet spends waiting in the output buffer for the outgoing link

When calculating the transmission delay with multiple routers, it is assumed that the propagation delay is 0.

Another day of class

Week 2.1 - Jan 10


Language defines how communication takes place. Sentences (sequence of symbols) of a language have:

  1. Syntax (also called grammar)

    • Can think of it as the form of the language

  2. Meaning (also referred to as semantics)

In a network, communication is between peer processes (entities) on different machines (usually). (Two or more processes using the same protocol are called peers).

Network Protocol

The set of rules that define the syntax and meaning of messages exchanged

Network functionality is partitioned into layers. This layering is called the network architecture. Each network layer is assigned a set of tasks and a protocol.

The Internet uses a 4 layer architecture.

Table 2. Internet layers, from top to bottom

Application layer

Transport layer

Network layer

Data Link layer

Physical layer (the Internet is never concerned with it though)

There is also the ISO-OSI architecture.

Table 3. The ISO-OSI architecture

Application layer

Presentation layer

Session layer

Transport layer

Network layer

Data Link layer

Physical layer

Mnemonics for remembering the OSI layers
  • Mnemonic #1 (bottom to top): Please Do Not Throw Sausage Pizza Away.

  • Mnemonic #2 (top to bottom): All People Seem To Need Data Processing.

The Internet architecture leaves the tasks of the Session layer and Presentation layer to the application.

Network Layers

Physical Layer

The physical layer moves data from the computer’s memory onto the "wire" (network media, could be unguided or wireless, does not have to be a wire) and vice versa.

This involves the encoding/decoding of digital data as electromagnetic signals.

Usually implemented by network interface hardware.

The data link layer moves data from computer to computer (device to device) across a single link. The link is a direct connection; it could be wireless, or a cable.

      Physical layer  Data link layer
         |            |
+------+ v            v         +------+
+------+                        +------+

This is implemented as a combination of network interface hardware and OS device drivers.

Data Link (Link Layer) addresses are hardware addresses. Hardware addresses are otherwise known as MAC addresses - Media Access Control. The hardware addresses reside in Read Only Memory in the NIC (Network Interface Card). (Read-only hardware addresses are particularly necessary in the case of broadcast links). This (MAC addresses) is actually the level of Local Area Networks.

Network messages are usually partitioned into frames/cells/packets/datagrams. Data link layers impose maximum size on a frame.

Network Layer (Internetwork Layer)

The network layer moves data from machine to machine across a series of links, possible spanning networks with different Data Link technologies and protocols.

4 nodes, spanning three different networks. Each possibly
using different data link technologies.

Bracket pairs denote networks.

|                               |
|   (o-----{o)------[o}-----o]  |
|                               |

The Network Layer is everything in the box.

The network layer protocol assigns a logical network layer address to each interface. Ethernet addresses are 48 bits (as are WiFi addresses). There is a protocol for translating between the MAC and logical addresses.

The Internet has 2 network layer protocols: IPv4, and IPv6 (IP stands for Internet Protocol). The logical addresses for IP are called IP addresses. IPv4 uses 32 bit addresses; IPv6 uses 128 bit addresses.

IPv4 addresses are 32 bits (4 bytes). Usually represented in Dotted Decimal Notation. Examples:, The address is the loopback address, represents "this machine"; refers to the local host (aka localhost).

Transport Layer

The transport layer moves messages from a process on one machine to another process on another machine.

The Internet has 2 transport layer protocols:

  • TCP (Transmission Control Protocol)

  • UDP (User Datagram Protocol)

Transport Layer addresses are pairs of (IP address, 16 bit port number).

The Transport Layer is implemented in the OS.

Table 4. Comparison of TCP and UDP

Connection-oriented reliable data-stream service


Bytes arrive in the same order as they are sent


Messages are not lost, corrupted, or duplicated

Connection Oriented
  • There is a setup phase that allocates resources at the sender and the receiver (or destination) to ensure packets are received correctly and in order

  • There are acknowledgments and retransmissions of packets

  • There is a teardown phase

Best effort delivery service

Best effort

Will not intentionally drop or corrupt packets.

UDP does not add anything to IP, except the ability to address processes (TCP does the same)

Lot of overhead, which affects performance

None of that overhead, so much, much faster

When programming, you only have to specify the destination address when creating the connection, not when sending every packet of data

When programming, you must specify the destination address with every chunk of data, because UDP is not connection oriented

There are two sockets that can just talk to each other (one socket on either end). The sockets can only talk to the socket to which they are connected.

There are two sockets, one on each end, but they do not have to talk to each other, and can talk to any UDP socket

When you receive data, you know where it came from

When you receive data, you have to look at the source address of each data packet


  • Transferring files

  • Financial transactions


  • Streaming

    • It is no big deal if you lose a couple of frames or milliseconds of audio

  • Some types of games

Application Layer

The Application Layer defines the format and meaning of messages that accomplish end user objectives.

Examples of Application Protocols
  • HTTP (HyperText Transport Protocol)

    • Protocol used by web servers to talk to their clients

    • Protocol for accessing resources on the web

    • Default port: 80

  • FTP (File Transport Protocol)

    • Default port: 21

  • Telnet

    • Used for sending command-line commands to a remote machine

    • Default port: 23

  • SSH (Secure SHell)

    • Similar to Telnet

    • Default port: 20

  • DNS (Domain Name System)

    • Assigns (human-readable) names (called domain names) to IP numeric addresses

      • Example:

    • DNS is a distributed database

    • DNS is an application layer protocol that translates between domain names and numeric IP addresses

    • Default port: 53

Writing Networked Applications

Most network applications are client-server apps, though some are peer-to-peer apps. There are also some hybrid applications.

Peer-to-peer means that the processes on the different machines are all playing the same roles relative to each other (they are executing equivalent code); that is, all processes send and receive the same protocol commands. Example: A networked tic-tac-toe game.

Client-server means that there are two different roles, clients and servers. Typically there is just one server, and one or more clients. The servers wait for client requests; the clients send requests and receive responses from the server. Example: A web server (the web browser is the client).

In a hybrid application, there are a bunch of peer programs, and a single server that connects the peers together. For example, a game; you send a request to the server, the server waits for someone else to send a request for a game, and the server tells you how to connect.

Writing networked applications requires an API to the transport layer services and to DNS. This is provided by the Sockets API. A socket is an abstraction for a network endpoint. Sockets are characterized by an IP address and a port number.


Ports in the range 0 to 1023 are reserved for well known services. A socket cannot be created with one of these port numbers unless the application is started with superuser or administrative privileges.

Another day of class

Week 2.2 - Jan 12

Socket API

A socket (network endpoint) is an abstraction for a programming language object that supports network communication.

There are two types of sockets:

  1. Passive Socket

    • Has an accept() method that is used to accept connection requests from active sockets

      • In Java/.NET, it is a blocking method

      • Returns an active socket that is connected to the calling client

    • Classes

      • Java - ServerSocket

            // Constructors
            ServerSocket(int port)
            /// Can use a string like "localhost" or a dotted-decimal
            /// IP address, like ""
            ServerSocket(String host, int port)
            ServerSocket(InetAddress address, int port)
            // Methods
            Socket accept()
            void close()
      • .NET - TcpListener

  2. Active Socket

    • Used to request a connection from a server socket and to effect actual communication upon connecting

    • Classes

      • Java - Socket

            // Methods
            void close()
            InputStream getInputStream()
            OutputStream getOutputStream()
            void shutDownInput()
            void shutDownOutput()
      • .NET - TcpClient

Socket Process Flow
  1. ServerSocket.accept() - called and blocking

  2. Client Socket.connect()

  3. ServerSocket.accept() returns a Socket

  4. All communication then uses this Socket

All active sockets on the server have the same IP address and port number as their parent ServerSocket. A TCP connection is identified by a 4 tuple: (Server IP, Server port, Client IP, Client port). The TCP stack on the client will assign an ephemeral (random) port number to the client; it exists to tell the connections apart.

A TCP connection is a duplex channel; each socket has an input stream (used to receive data from the connection) and an output stream (used to send data into the connection). This means that after the initial connection, TCP connections are reduced to I/O.

In Java, InputStream and OutputStream are the super classes for binary byte stream I/O (read and write bytes). Reader and Writer are the super classes for character stream I/O. InputStreamReader(InputStream is) converts is to a Reader; it allows you to invoke Reader methods on the InputStream PrintWriter(OutputStream os) converts os to a Writer that supports print(), println(). BufferedReader(Reader r) adds buffering capability to the Reader (eg String readLine()).

Example: Networked Calculator

Protocol commands sent to the server by clients:

  • prod x y

  • sum x y

  • diff x y

  • quotient x y

  • square x

  • bye

Servers should allow concurrent connection to clients (multiple clients can connect simultaneously), but our example allows one client at a time.

void main() {
    ServerSocket serverSock = new ServerSocket(50001);
    while(true) {
        Socket sock = serverSock.accept();
void handleClient(Socket sock) {
    BufferedReader bR = new BufferedReader(new InputStreamReader(sock.getInputStream()));
    PrintWriter pW = new PrintWriter(sock.getOutputStream(), true);
    // Loop until "bye"
    //   Use bR.readLine() to read command
    //   Interpret command
    //   Write result to pW
    // Close socket
Another day of class

Week 3.1 - Jan 17


GUIs have:

  1. Main Window

  2. User Interface Components

  3. Layout mechanism for arranging UI components

    1. Uses containers

  4. Event handlers/listeners

JavaFX approach

Application class represents a JavaFX application. Has methods:

  • static void launch(Class<Application> app, String[] args)

  • static void launch(String[] args)

  • void init()

  • void start(Stage st)

  • void stop()


  • Creates an instance of your subclass of Application

  • Calls init() on it

  • Creates a Stage

  • Passes it to start() on the GUI thread (application thread)

JavaFX uses a theatre metaphor — there are multiple players on a stage.


Stage is (associated with) a top level window.

  • void setScene(Scene scene)

  • void setTitle(String t)

  • void show()


Scene is the container for a Scene graph.

  • Scene(Parent root)

  • Scene(Parent root, double width, double height)

Simplest form of a Scene graph: tree of Node objects. A Node object corresponds to a UI component that is visible on the screen. Therefore, Node is the superclass of all user interface components.

Inheritance hierarchy

(1) * Object
(2) ** Node
(3) *** Canvas
(3) *** Parent
(4) **** Control -- UI component that can interact with the user
(5) ***** Labelled
(6) ****** Label
(6) ****** ButtonBase
(7) ******* Button
(7) ******* CheckBox
(7) ******* ToggleButton
(8) ******** RadioButton
(4) **** Region
(5) ***** Pane
(3) *** ImageView
(3) *** Shape


Pane is a container that exposes the list of its children. Pane has a method ObservableList<Node> getChildren().

ObservableList has methods
  • add(Node child)

  • addAll(Node …​children)

The Pane class has an instance method void setPadding(Insets value). Most subclasses of Pane have a method static void setMargine(Node child, Insets )value).

Panes and Component Layout

VBox: Stacks its children vertically. Has a constructor VBox(double vgap) that will add a gap between its children.

HBox: Stacks its children horizontally. Has a constructor HBox(double hgap) that will add a gap between its children.

BorderPane: like using a BorderLayout in Java Swing.

|               Top               |
|      |                  |       |
| Left |      Center      | Right |
|      |                  |       |
|             Bottom              |

BorderPane has methods void setTop(Node child), void setBottom(Node child), etc.

GridPane: You just start adding children, and say what row and column to add the child to; the grid will automatically be extended. There can be empty cells. void add(Node child, int column, int row).


class MyJavaFXApp extends Application {
    public static void main(String[] args) {
    public void init() {
        System.out.println("Initialization phase");
    public void start(Stage stage) throws Exception {
        Label label = new Label("CSC 469 is a blast!");
        Scene scene = new Scene(label, 300, 150);
        stage.setTitle("Java FX is fun!");;


  • void setAlignment(Pos value)

    • It is an enumeration type:

      • TOP_LEFT



      • TOP_CENTER

      • TOP_RIGHT

      • CENTER




Margin and Padding

Margin: Determines how far away a node is from its neighbors.

Padding: Determines how much space there is around the content.

Margin and padding are set by objects of type Insets.

  • Insets(double width)

  • Insets(double top, double right, double bottom, double left)

Event handling

JavaFX has a generic EventHandler interface

interface EventHandler<EventType> {
    public void handle(EventType e) {


Event bubbling works similarly to JavaScript — event handlers can be attached to containers as well as UI elements themselves.

Another Sample
    public void start(Stage primaryStage) {
        Button btn = new Button();
        btn.setText("Say 'Hello World'");
        btn.setOnAction(new EventHandler<ActionEvent>() {
            public void handle(ActionEvent event) {
                System.out.println("Hello world!");
        StackPane root = new StackPane();

        Scene scene = new Scene(root, 300, 250);

        primaryStage.setTitle("Hello World!");
Another day of class

Week 3.2 - Jan 19


An exception is a condition that occurs during execution of a program that makes normal continuation of execution impossible. Exceptions are run-time errors. Examples:

  • DivideByZeroException

  • FileNotFoundException

  • NullPointerException

If a function is declared as throwing an exception, or a particular kind of exception (such as FileNotFoundException), then the compiler will use that information and check that there is a try { ... } catch(...) { ... } for that particular exception; or, if the exception is not caught (or is rethrown), the function has to be declared as also throwing that exception. Checked exceptions cannot be prevented by careful programming; unchecked exceptions, such as NullPointerException or ArrayIndexOutOfBoundsException are preventable.

To catch an exception:

try {
    // Code that could throw an exception E
} catch( E exception) {
    // Code to handle exception


A thread is a separate flow of control within an executing program, ie the sequence of instructions that is executed when a function is called. The function is called the start method of the thread.

"All" programs start with a single thread. A thread may start another thread.

Main thread
   |\ <-- create thread
   | \
   |  \
   |   \
   |    \
Main     New thread

Java - Thread class.

constructor: Thread(Runnable target)

method: void start()

Interface Runnable: has function void run(). As it takes no parameters, parameters to the function being called need to (should be) passed to the (custom) constructor of the Runnable. See example below.

Example 1. Creating a thread
class MyRunnableClass implements Runnable {
    MyType x;
    public MyRunnableClass(MyType x) {
        this.x = x;
    void run() {
        // Access X here
public class MyThreadProg {
    static void main(String args[]) {
        MyType p = new MyType(...);
        Thread th = new Thread(new MyRunnableClass(p));
        // ...
        // ...
        // Continue execution of main thread
        // ...
        // ...
Another day of class

Week 4.1 - Jan 24

Connect 4 program

Application protocol

play <col>
chat <message>

Building the user interface

                        Top: Menubar
Left: Game board (grid pane)       Right: Chat history (text area)
        Bottom: Box for chat visibility, and status bar
Steps to create Menus
  1. Create a menu bar

  2. Create menus and add menus to menu bar

  3. Create menu items and add to menus

  4. Add event handlers to menu items or menus

Menus for program
  • Game menu

    • Server role

      • Alert box, set up a server socket, wait for connection, set up buffered reader, print writer, and game state.

    • Client role

      • Alert box, ask for server IP, connect to server, set up reader, writer, game state

  • Play again

  • Quit

Next Steps

Isolate important events (UI events) and add event handlers.

  • playagain menu (only visible in between games)

    • Send a playagain protocol command

  • quit menu

    • Send quit protocol command

    • Shutdown input on socket

    • Exit

  • Send message button

    • Copy chat message from text field to chat history

    • Send message to other side

  • Mouse enter/exit on Circle objects in top row

    • Implementation left as an exercise for the reader

  • Mouse click on Circle object

    • Check if room in column

    • If room

      • Drop a ball

      • Send play <col> message

      • Check for win

        • Win

          • Activate playagain menu item

        • No win

          • Is board full? …​

Receiving messages from the remote side is complicated by

  1. UI components can only be handled on the GUI thread (not thread safe)

  2. You should not perform blocking I/O on lock tasks on the GUI thread

GUI systems often have a facility for a non GUI thread to ask that some work be done in the GUI thread.

Create a thread to read network input and post work to the GUI thread. Outline of thread’s main method:

String netInput = netReader.readLine();
while(!netInput.equals("quit")) {
    Platform.runLater(new Runnable parametrized by netInput)
    netInput = netReader.readLine();
Platform.runLater(handle quit message)


class PlayerMarker extends Circle {
    public final int row, col;
    public PlayerMarker(int r, int c) {
        row = r; col = c;
    public Player player;
    void setPlayer(Player p) {
        player = p;

Then create a square matrix PlayerMarker cells[7][7], which will then eliminate the issue of getting the children of the grid pane (by instead iterating across cells).

Another day of class

Week 4.2 - Jan 26


DNS (Domain Name Service) is a protocol, a service, and a hierarchical database. It translates hostnames to numeric IP addresses (so that people don’t have to remember the IP address for each device/website/etc they want to use).

DNS is an application layer protocol that runs on top of UDP, port 53.

Application (HTTP, mail client, etc) sends a DNS query to a DNS server, and waits for a reply.

The database stores Resource Records (RR). For example:

  • Type A — stores mapping of host name to address

Some services provided by DNS

  1. Translation of hostnames to IP addresses

  2. Host aliasing — the ability to have different hostnames resolve to the same IP address. One of these names is the canonical hostname.

  3. Load distribution/load balancing. DNS can associate multiple IP addresses with the same canonical hostname. A DNS reply to a DNS query for a hostname returns the canonical hostname plus the list of IP addresses.

  4. Mail server aliasing — this allows "nicer" hostnames in email addresses

Programming language interface (API) to the DNS protocol:

  • .NET platform — Dns class

  • Java platform:

    • InetAddress class

      • Inet4Address

      • Inet6Address

    • Instance methods of InetAddress

      • byte[] getAddress()

      • String getCanonicalHostname( )

    • Static methods

      • static InetAddress getByName(String host)

      • static InetAddress[] getAllByName(String host)

      • static InetAddress getLocalHost()

DNS database/DNS service is distributed over many DNS server machines. There are 3 levels:

  1. Root DNS servers (~400 over the entire planet)

  2. Top level domain servers (TLD)

    • Top level domains

      • .com — (for profit organizations)

      • .org — (meant for nonprofit organizations)

      • .net — (network services providers)

      • .int — (international organizations)

      • .edu — (educational institutions)

      • .gov — (federal and state government/US)

      • .mil — (military organizations)

    • Also TLDs for countries

  3. Authoritative DNS servers

    • These are the DNS servers for individual organizations with an Internet presence

Local DNS Servers: Provided by an ISP for organizational or residential customers that don’t want to administer their own DNS server.

2 types of DNS queries
  1. Recursive queries (figure 2.20 in the book)

  2. Iterative queries (figure 2.19 in the book)

There are different types of Resource Records, such as Type A, NS, CNAME, MX. All RR are 4-tuples (<name>, <value>, <type>, <ttl> [time to live]).

Type A is for "address". (<hostname>, <IP address>, A, <TTL>)

Type NS ("Name server"). These records are used to direct a DNS query to an authoritative name server. (<hostname>, <hostname of authoritative name server>, NS, <TTL>)

Type CNAME ("canonical name"). These records map an alias to its canonical name. (<alias>, <canonical hostname>, CNAME, <TTL>).

Type MX ("Mail server aliasing"). (<alias>, <mail server canonical name>, MX, <TTL>).

Format of DNS queries and replies:

         <--- 32 bits --->
| Identification  |      Flags       |      12 byte header
|                 |                  |
|                 |                  |
|                                    |
|                                    |
|                                    |
|                                    |
|                                    |
|  Rest of data                      |
|                                    |
|                                    |
|                                    |
|                                    |

Transport Layer

  1. Extends the host-to-host delivery service that is provided by the network layer to a process-to-process delivery service.

  2. May provide additional services, such as

    • Integrity checking (TCP and UDP do this)

    • Reliable data stream service (ie does not lose, corrupt, reorder, or duplicate packets)

Another day of class

Week 5.1 - Jan 31

More info on Connect 4 program

To run a second instance of the program in Netbeans: Right click on the file → Run file.

Play again menu should have two options, "Yes" and "No", and the Quit menu can be eliminated.

Once connected, the "Game Setup" menu should be disabled.

Additional pointers:

To have global variables, create a class (in a separate file) that is filled with public static members.

The game grid will have nodes that you didn’t put in there, so when iterating across all of the children of the grid, you need to filter out children that are not Circles.

If you rethrow an Exception as a RuntimeException, it will terminate the application (unless that exception is also caught).

You can close the writer, and close the reader, but don’t close the socket, because it will throw an exception on the other side.

Reliable data transfer

Reliable data transfer can be implemented at different layers:

  • Data link layer

  • Network layer

  • Transport layer

  • Application layer

TCP has built-in flow control, so that a fast sender does not overwhelm a slow receiver. It also has built in congestion control, so that if there is congestion in the network, the sender will slow down. These things add overhead.

Book model:

General case Specific example

Upper layer

Application layer

RDT layer


UDT layer (unreliable channel)

IP (unreliable)

Primitives used in the book while describing implementation of reliable data transport:

  • rdt_send(data)

    • Callback implemented by RDT and made available to (called by) the upper layer

  • udt_send(packet)

    • Callback implemented by the unreliable data transfer channel and called by the RDT layer

  • rdt_rcv(packet)

    • Implemented by RDT, and a callback that is called by UDT to pass a packet to the RDT layer. ( rcv ⇒ receive )

  • deliver_data(data)

    • Called by RDT to deliver data to the upper layer; callback implemented by the upper layer

Protocol implementation

Implementation of protocols is based on mathematical models called Finite State Machines (FSM). An FSM is a machine that has a finite set of states (a state represents something the machine wants to remember about the task being performed) and a transition function (map) (state, event) -→ (state, action). At any given time, the FSM is always in exactly one state. At each state, certain events may occur — the FSM performs an action and transitions to a new state (which may be the same as the old state). There is an initial state.

RDT 1.0: RDT over a reliable channel.

Sending side and receiving side both have a FSM, and the FSM only has one state:

Sending side:

Wait for call from above

packet = make_packet(data)

Receiving side:

Wait for a call from below

extract(packet, data)

RDT 2.0: RDT over a channel with bit errors

If bit errors occur, then there needs to be a way to detect them.

Recovering from bit errors requires:

  1. Error detection

    • Sender includes checksum

    • Receiver checks checksum

  2. Receiver feedback

    • Receiver must inform sender whether errors occurred)

  3. Sender retransmission

Types of receiver feedback

  1. Positive acknowledgments (ACK)

    • Receiver tells the sender that it receives a packet with no errors, then the sender proceeds to send the next packet

  2. Negative acknowledgments (NAK)

    • Receiver tells the sender if it receives a corrupt packet

ARQ protocol — Automatic Repeat reQuest. Protocol in which senders automatically retransmit a packet for which a NAK is received.

Stop and wait protocol — sender stops and waits for an acknowledgment before transmitting the next packet.

Diagram in book for RDT 2.0

Another day of class

Week 5.2 - Feb 02

RDT 2.1

Unreliable data transfer channel can corrupt and/or lose packets.

Dealing with these problems requires:

  1. Checksums (detect errors)

  2. Receiver feedback (ACK/NAK)

  3. Sender retransmission

Packet loss requires a timer set for a packet. Sender retransmit on timeout or a NAK, or on a corrupt packet from the receiver. Retransmission may result in duplicate packets arriving at the receiver. Sequence numbers are thus needed to detect duplicates.

For stop and wait protocols, a 1 bit sequence number is sufficient — these are called alternating bit protocols.

Another day of class

Week 6.1 - Feb 07

RTT (Round trip time) — time from transmission of a packet to reception of its ACK

Mechanisms for implementing RDT
  1. Checksums

  2. Receiver feedback

  3. Timers

Also need to know:

  • ARQ

  • Alternating bit protocol

  • Stop and wait protocol

Drawbacks of stop and wait:
  1. Poor network utilization

    • You are transmitting for a very short period of time, and then are waiting for a response.

    • Example:

      • 1 Gbps link

      • Transmission rate of 0.08 milliseconds for a packet of typical size

      • Network utilization is (L / R) / (RTT + [L / R]) where L / R is transmission delay

      • RTT is approximately 30 milliseconds for a packet to travel from New York to California

      • So the network utilization would be 0.08 / 30.08 = 0.00027

NAK free protocols — the receiver sends a positive acknowledgment for the last packet that was correctly received, upon receiving any packet, regardless of if it was corrupted or not. The sender will send the packet just after the sequence number being acknowledged. A corrupted ACK will be ignored, and the packet will be resent when the timer times out.

Pipeline protocols

Pipelined protocols permit a sender to have up to N packets outstanding before stopping to wait for an ACK.

2 categories (approaches) to pipelined protocols:

  1. Go-Back-N (GBN)

  2. Selective Repeat (SR)

General info on pipeline protocols:
  1. Require a X bit sequence # field

    • Sequence number space is 0..2X - 1

  2. Sender requires a buffer for transmitted packets not yet ACK’ed

    • The receiver may buffer correctly received packets

      Sliding window protocol

      At any given time, there is only a window of contiguous sequence numbers available. This window changes over time, thus the name 'sliding window'.

Go Back N

GBN sender

The sender has the following view of the sequence number space:

sent and ACK'ed                         not currently usable
 |          next sequence number               |
    base                             base+N-1

base..nextSequence-1 : packets with these numbers have been transmitted but are waiting to be acknowledged.

nextSequence : the sequence number for the next packet to be sent (if it’s available).

nextSequence..base+N-1 : Sequence numbers that can be immediately used.

Packets can only be sent in the range base..base+N-1

GGN uses a single timer that is associated with the base sequence number; when the timer times out, GBN will assume that all of the packets from base..nextSequence have been lost, retransmit all of them, and restart the timer.

There are 3 events, but only 1 state.

Call from above (to send data)

if(nextseqnum == base + N) {
    hold on to the packet for later transmission
} else {
    send packet;
    start timer;

Receive an ACK

if(ACK is corrupt) {
    do nothing;
    // wait for timer to time out
} else {
    let s = sequence number in the ACK
    base = s + 1
    if (base == nextseqnum) {
        stop timer

The timer times out

resend packets base .. base + nextseqnum - 1
start timer
GBN Receiver
  1. GBN receiver does not buffer packets

  2. It has an expected sequence number

  3. Has only one event

    • Event: Receive a packet

      • If a packet is corrupt or has the wrong (unexpected) sequence number, then the receiver discards the packet. Send an ACK for the last correctly received (not corrupted, and was the expected number) packet

      • Else, pass the packet to the upper layer, send an ACK for the packet’s sequence number.

Facts on GN receiver
  • Sends an ACK for sequence number X if X and all preceding packets have been correctly received and passed to the upper layer.

  • GBN uses _cumulative acknowledgment

Selective Repeat

  • The receiver buffers out of order packets and passes a contiguous block of packets to the upper layer.

  • Receiver sends individual ACKs

The receiver has the following view of the sequence number space:

recieved and ACK'ed
and passed to upper layer                discarded
 |          next sequence number               |
 |  recvbase                             recvbase+N-1
as long as the received packet
is no more than N behind, an
ACK must be sent for the packet

The sender has the following view of the sequence number space:

sent and ACK'ed                         not currently usable
 |          next sequence number               |
    sender_base                         sender_base+N-1

sender_base : sequence number of packet with lowest sequence number among those sent, but no ACK received.

sender_base .. nextSequence-1 : transmitted, some of them have been ACKed

SR sender uses a separate (individual) timer for each packet sent; when the timer times out, only that specific packet will be retransmitted.

Page 228, figures 3.24 and 3.25 summarize the SR sender and receiver FSMs.

Implementation of TCP

TCP is connection oriented. A TCP connection is dedicated to 2 processes.

Another day of class

Week 6.2 - Feb 09

TCP is a reliable byte stream service. It divides a stream of bytes into TCP segments.

MSS — Maximum Segment Size for the TCP segment.

A TCP segment has to be enclosed in an IP datagram, which is enclosed in a Data Link Layer frame.

Data Link Layer Frame
| Data Link Header | IP header | TCP header | User data (payload) |

Data Link Layers define an MTU (Maximum Transfer Unit), the maximum number of bytes in a DL frame.

TCP estimates an MSS based on the MTU of the local DL layer.

Structure of the TCP segment:
              32 bits
    16 bits           16 bits
|  Source port   |    Dest port   |
|           Sequence #            |
|          Acknowledgment #       |
| 1  |  2  |  3  | receive window |
|Inet Checksum   |Urgent Data Ptr |
| Variable length options         |
|            Data (payload)       |
|               ...               |
|               ...               |
|               ...               |

1: header length (4 bits)
2: unused (6 bits)
3: flags (6 bits)

The sequence number is the number (offset) of the first byte in the segment. (This means that sequence numbers are not necessarily consecutive). Acknowledgment number — number of the next byte expected by the receiver. Each segment has a segment number and optionally an ACK number.

Header Length (4 bits) — size of the header in 32 bit words.


  • URG

    • Urgent

    • The segment contains urgent/critical data at the offset given by urgent data pointer

  • ACK

    • Acknowledgment

    • ACK = 1 — Acknowledgment field is valid

  • PSH

    • Push

    • Receiver should pass the segment to upper layer immediately

  • RST

    • Reset — closing the connection

  • SYN

    • Synchronize

    • SYN=1 - first segment from a client requesting a connection

  • FIN

    • FIN=1 — sender is about to terminate the connection

Receive window — used for flow control and congestion control (but mainly for flow control)

TCP uses cumulative acknowledgments.

TCP uses timers — a single timer associated with the lowest numbered byte in the stream that has been transmitted but hasn’t been acknowledged yet.

Determining the timer interval:

TCP maintains a variable EstimatedRTT.

SampleRTT for a segment is the RTT for that segment. At any given time, TCP is only sampling the RTT for a single segment (for a connection).

To compute EstimatedRTT, use an exponential weighted average of the SampleRTT’s.

Take an alpha @ where 0 < @ < 1
@ * a1 + [ (1 - @) * a2 ]

EstimatedRTT = (1 - @) EstimatedRTT + @ * SampleRTT.

Initially EstimatedRTT = SampleRTT.

Recommended value for alpha is 1/8.


7/8 S1 + 1/8 S2

7/8 (7/8 S1 + 1/8 S2) + 1/8 S3 = (7/8)^2 S1 + 7/8 * 1/8 S2 + 1/8 S3

(7/8)^3 S1 + (7/8)^2 * 1/8 S2 + 7/8 * 1/8 S3 + 1/8 S4

EWA — Exponential Weighted Average — gives more weight to the recent samples.

DevRTT — an estimate of the running deviation in the RTT. DevRTT = (1 - beta) * DevRTT + beta * (SampleRTT - EstimatedRTT). Recommended beta is 1/4.

Set the timer interval to EstimatedRTT + DevRTT.

Simplified TCP implementation

Sending side
NextSeqNum = initialSeqNum;
SendBase = initialSeqNum;
loop forever {
    switch(event) {
        event : data received from app
            create TCP segment sequence
            send segment
            NextSeqNum += length of the data
            start timer

        event : timer times out
            retransmit the segment at SendBase
            start timer

        event : ACK received with ACK # y
            if ( y > SendBase ) {
                SendBase = y
                if ( there are unacknowledged segments ) {
                    start timer

How TCP tunes its performance

Three events
  1. Timeout

    • Double the timeout interval

  2. ACK

    • Set timeout interval by the previously mentioned formula

  3. Data from above

    • Set timeout interval by the previously mentioned formula

Doubling the timer interval on timeout is called exponential backoff. This is part of TCP congestion control.

Fast Retransmit

A TCP sender that receives three ( 3 ) ACKs for a segment will retransmit the segment without waiting for a timeout. The TCP receiver sends an ACK for the last correctly received segment when a segment is received that is correct but out of order.

Given segments
1 2 3 4
And segment 2 is lost
The received order will be
1 3 4
So the sender will receive 'ACK 1' 3 times
And the sender will then retransmit 2 immediately without waiting for the timer to time out.

TCP connection setup

Setting up a TCP connection involves a 3 way handshake, ie 3 TCP segments are exchanged between the client and server to establish the connection.

  1. Client selects an initial sequence number, clientSeqNum. Send a segment with SYN=1. This is called the SYN segment.

  2. The server sends an acknowledge number, which is clientSeqNum+1. And it sends its own sequence number, serverSeqNum. Also, SYN=1, ACK=1. This is called the SYNACK segment. Server allocates buffers and state for the connection.

  3. Client sends SYN=0, sequence number = clientSeqNum+1, ACK = serverSeqNum+1. Client allocates buffers and state for the connection.

Security vulnerabilities

The client does not have to allocate any resources when asking for a connection, but the server has to allocate resources to grant the connection, even though the connection is not actually completed until the server receives the final segment.

Denial of service attack — called a SYN flood attack. A client sends a SYN segment but never completes the connection, thus causing the server to allocate resources that are never used.

A distributed DOS (DDOS) attack involves using a vast number of machines to perform SYN floods.

Another day of class

Week 7.1 - Feb 14

2 functions of the Network Layer

  1. Routing

  2. Forwarding

Routing — global network-wide process where all routers run distributed routing algorithms (based on routing protocols) to determine end-to-end paths for packets to follow.

Routing protocols
  • BGP

  • RIP

Routing is performed in the control plane.

Routing table is built by the routing algorithms, and contains information used to configure the forwarding table.

Forwarding — local process of examining a packet to determine the outgoing link to send it on.

Forwarded occurs in the data plane. The data plane is usually implemented in hardware.

Forwarding table is a map of destination address ⇒ outgoing interface.

Routing and forwarding — depends on routing tables and forwarding tables.

SDN — Software Directed Networking

New router architecture.

Centralized remote controller, and multiple routers. The remote controller is in a high speed data center — communicates with the routing components to exchange routing information. The remote controller computes the routes based on the information it receives and updates the routing components in other routers. It is implemented in software.

Network Layer Service Models

  1. Guaranteed delivery — packets are not lost

  2. Guaranteed delivery with bounded delay

  3. In-order packet delivery

  4. Guaranteed minimal bandwidth

  5. Security — confidentiality

IPv4 offers none of these services.

ATM networking technology: Asynchronous Transfer Mode. It’s a physical layer, data link layer, and network layer technology. It uses virtual circuits/is circuit switched.

Packet switches

Switching and forwarding are synonymous terms.

Packet switch makes forwarding decisions based on examination of packet headers.

Link Layer or Layer 2 switch forwards packets based on Link Layer headers. Example: Ethernet switch.

A router forwards packets based on Layer 3 header info.

Inside a router:
  1. Routing processor

  2. Input ports

    • Input/output pair for each link/interface

  3. Output ports

  4. Switching fabric

Each input port has 3 components:

  • Input port

  • Routing processor

    • Control packets go through here

  • Switching fabric

    • Data packets go through here

    • Output ports are connected

Control packets — carry routing information from running routing protocols.

The forwarding tables reside in the input ports.

Switching fabric — conveys packets from input port to output port.

The 3 components in the input port:

  1. Line terminator implements the physical layer, converts between electromagnetic signals and digital data.

  2. Data Link processing component.

  3. Takes care of the forwarding table lookup, actual forwarding, and queuing.

3 2 1 components on output are similar to those of the input port, except 3 is mostly queueing.


Destination based forwarding — action in incoming packet depends on where the packet is going.

Generalized forwarding — action on incoming packet may depend on other header fields as well as destination.

Management of forwarding tables

Forwarding tables store mappings key→value, d→i

d = destination address

i = interface to send out on

IPv4 addresses — there are 232 , or about 4 billion IPv4 addresses.

To reduce the size of forwarding tables…​

IP addresses are assigned to networks in contiguous blocks with common prefixes. The common prefix is called a network prefix.

Forwarding tables map destination network prefixes to outgoing interface. This, together with route aggregation, works to reduce the size of forwarding tables.

Each router’s forwarding table will map a set of network prefixes to specific interfaces. There is a default interface and all other network prefixes that are not specifically mentioned go out this default interface.

Another day of class

Week 7.2 - Feb 16



Connection setup requires sender and receiver addresses

No connection phase. Each packet has its own source/destination address

Reliable byte stream delivery service

Unreliable packet delivery service

Specifying address info:

  • InetAddress, port number

  • SocketAddress — combines InetAddress and port number

Need 2 Java classes for UDP:

  • DatagramPacket

  • DatagramSocket

    • Server socket is bound to IP address and port number (developer specifies port)

    • Client socket — ephemeral port is assigned

DatagramPacket has a:

  • byte buffer

  • offset into the buffer

  • length

DatagramPacket has constructors:

  • DatagramPacket(byte[] buff, int offset, int length)

    • For receiving

  • DatagramPacket(byte[] buff, int length)

    • For receiving

  • DatagramPacket(byte[] buff, int offset, int length, InetAddress addr, int port)

    • For sending

  • DatagramPacket(byte[] buff, int offset, int length, SocketAddress addr)

    • For sending

For sending, DataPackets need to specify the receiver address information

  • Sender IP and port

  • Receiver IP and port

DatagramPacket methods:

  • InetAddress getAddress()

  • int getPort()

  • byte[] getData()

  • int getOffset()

  • int getLength()

  • void setData(byte[] buff, int offset, int length)



  • DatagramSocket()

    • For UDP client

  • DatagramSocket(int port)

    • For UDP server


  • void bind(SocketAddress addr)

  • void connect(InetAddress addr, int port)

  • void disconnect()

  • void close()

  • InetAddress getInetAddress()

    • Returns the address of remote connected socket

  • SocketAddress getRemoteSocketAddress()

  • void send(DatagramPacket)

  • void receive(DatagramPacket)

Dealing with byte buffers

If using a text-based protocol, we need to convert between character strings and byte arrays.

String class has:

  • byte[] getBytes()

  • String(byte[] buffer, int offset, int length)

UDP-based calculator service

// receive buffer and server socket
byte[] buffer = new byte[1024];
DatagramSocket serverSock = new DatagramSocket(50002);
while(true) {
    // wait for a packet
    DatagramPacket recvPack = new DatagramPacket(buffer, buffer.length);
    // process the packet
    String cmd = new String(recvPack.getData(), 0, recvPack.getLength());
    Scanner sc = new Scanner(cmd);
    String opcode =;
    int x,y,result = 0;
    switch(opcode) {
        case "add":
            x = sc.nextInt();
            y = sc.nextInt();
            result = x+y;
    byte[] sendBuffer = String.valueOf(result).getBytes();
    DatagramPacket sendPack = new DatagramPacket(sendBuffer, 0, sendBuffer.length, recvPack.getRemoteSocketAddress());
DatagramSocket sock = new DatagramSocket();
byte[] recvBuffer = new byte[1024];
Scanner sc = new Scanner(;
while(true) {
    System.out.println("Enter a command, or 'bye'");
    String input = sc.nextLine().trim();
    byte[] sendBuffer = input.getBytes();
    DatagramPacket sendPack = new DatagramPacket(sendBuffer, 0, sendBuffer.length, InetAddress.getByName("localhost"), 50002);
Another day of class

Week 8.1 - Feb 21

Homework 4

User Interface Modification (from Connect 4 project)

Connect Menu

  • Get foreign IP address, port #

  • Get local port #

  • Set up DatagramSocket

Upload Menu

  • File Chooser to select a file

    • Google "JavaFX File Chooser"

  • Display image in local ImageView

  • Send image to the other side

JavaFX Images

Image — in-memory representation of an image.

Image(String URL)
Image(String filename)
Image(InputStream is)

ImageView — wraps Images in a Node object.

ImageView()  .setImage(Image i)
ImageView(Image im)
ImageView(String URL)


Binary protocol with 3 commands.

  • [chat] [<message>]

  • [quit]

  • [photo] [length in bytes] [image-bytes]

    • Length is a long int.


It is a filter OutputStream (put it on top of another output stream).

void writeLong(long x) will write a long as 8 bytes.

void writeUTF(String str)


It is a filter InputStream.

long readLong() will read a long as 8 bytes.

String readUTF()


new ByteArrayInputStream(byte[] buf) — creates a ByteArrayInputStream so that it uses buf as its buffer array.


It allows you to write a stream of bytes that is kept in memory.

Has a method byte[] toByteArray()

The idea is that you create a ByteArrayOutputStream, write all of the bytes in the image into the stream.

Another day of class

Week 9.1 - Feb 28

Internet Protocol

IPv4 Datagram Format

              32 bits
    16 bits           16 bits
| 1  | 2  |  3   |   4            |
|  16 bit ID     | 5|6|7|  8      |
| 9    | 10      | 11             |
|    32 bit source IP address     |
|  32 bit destination IP address  |
|    Variable length options      |
|            Data (payload)       |
|               ...               |
|               ...               |
|               ...               |

The 1st word of the header:
1:   4 bits, IP version - either 4 or 6, for IPv4 or IPv6
2:   4 bits, header length, in 32 bit words.
     Maximum header length is 15*4 = 60 bytes.
3:   8 bits, TOS (Type of Service); usually not used.
     Routers could use this field to provide a type of service
4:   16 bits, datagram length in bytes

The 2nd word of the header deals with fragmentation and reassembly.
5:   3 bit field, not used
6:   1 bit, DF field, means "do not fragment".
     If set to 1, it means the datagram cannot be fragmented.
     If dropped, the router sends an ICMP message to the source router.
7:   1 bit, MF field, means "more fragments".
     If set to 1, it means this datagram is not the last fragment.
     If set to 0, it means this datagram is the last fragment.
8:   Fragmentation offset.
     The offset of this fragment from the beginning of the original datagram.
     Used by the destination router to reassemble the fragments.

The 3rd word of the header:
9:   8 bits, TTL (Time To Live), also called "hop count limit".
     The maximum number of routers that can forward this datagram.
     Set by the initial router.
     Decremented by each router.
     Dropped when it is down to 0.
10:  8 bits, Protocol.
     Identifies the protocol of the message being carried in the payload.
     Numbers indicate TCP, UDP, ICMP, etc
11:  16 bit header checksum.
     Recomputed at every router.

The minimum size of the header is 5 32-bit words, so there is a 20 byte minimum for the header.

ICMP — Internet Control Message Protocol

It is a layer 3 protocol that is used by routers for network state and error reporting.

ICMP messages are carried inside of IP datagrams in the payload field.

IPv6 Datagram Format

              32 bits
    16 bits           16 bits
| 1 | 2     |         3           |
|  4             | 5    | 6       |
|                +                |
|    128 bit source IP address    |
|                +                |
|                +                |
|                +                |
|  128 bit destination IP address |
|                +                |
|                +                |
|            Data (payload)       |
|               ...               |
|               ...               |
|               ...               |

The 1st word of the header:
1:   4 bits, IP version field
2:   8 bits, Traffic Class, same as TOS field in IPv4
3:   20 bits, flow label.
     Meant to identify a stream of datagrams that 'belong together',
     that belong to the same 'flow'. Currently nobody uses it.

The 2nd word of the header:
4:   16 bits, Payload length, same as the datagram length.
5:   8 bits, Next Header, same as the protocol field in IPv4.
6:   8 bits, Hop Limit, same as TTL in IPv4.

IPv6 does not support options, which means it has a fixed size header (10 32-bit words, 40 bytes).

IPv6 does not support fragmentation/reassembly. This is because routers spend a lot of time fragmenting datagrams and reassembling them at the destination.

IPv6 does not have a checksum. This is because routers spend time computing it, and because the data link layer underneath has a checksum, and the upper layer protocol has a checksum, so there’s "no need" to have another checksum in the middle.

IPv4 vs IPv6

IPv6 nodes also run IPv4. However, IPv4 nodes cannot talk to IPv6 nodes. IPv6 datagrams can tunnel through IPv4 (Protocol Tunnelling).

Tunnelling — when protocol data units for a protocol P1 are carried by protocol P2 data units as data.

 [ P2 header (P1 PDU) ]

The IPv4 protocol field has a value for IPv6 as the "upper layer" protocol.

IP addresses are assigned to nodes via:

  • Static IP addresses

  • DHCP (Dynamic Host Configuration Protocol).


DHCP: Application layer protocol running on UDP on port 67. DHCP configures network interfaces with:

  • IP address

  • Network prefix mask

  • IP addresses of DNS servers

DHCP messages:

  • DHCP discover messages

    • Sent out by a node that is booting and needs its interfaces configured.

    • This is a broadcast message.

  • DHCP offer messages

    • Broadcast by all DHCP servers that receive a DHCP discover message.

    • Contains an IP address + configuration information + a lease period

  • DHCP request message

    • Sent by a node that receives a DHCP offer message to request the offered IP address.


    • Sent by the DHCP server to ACK the request.

Private IP addresses

Private IP networks are insulated from the global Internet.

There are 3 ranges of private IP addresses:

  • -


    • Total of 216 IP addresses.

  • -


    • About 1 million IP addresses

  • -


    • About 17 million IP addresses

Private IP addresses are not routable on the public internet.

NAT — Network Address Translation

Requires a NAT enabled router. The router has a routable IP address assigned by the ISP. A NAT router has a NAT translation table that maps (Private IP address, port x)(Public IP address, port y). This means the NAT router can support up to about 65000 connections at any given time to the same destination IP.

Routing algorithms

Two types of routing algorithms:

  • Centralized Routing Algorithms (also called Link State Algorithms)

    • Node running the algorithms requires complete knowledge about the entire network

  • Distributed Routing

    • Node only requires information about directly connected networks

    • Each node only exchanges information with its neighbors

Distributed algorithms are called distance-vector algorithms.

Another classification of algorithms:

  • Load-sensitive algorithms

    • They run every time they 'sense' a change in network conditions

  • Load-insensitive algorithms

Link state (LS) algorithm — based on Dijkstra’s algorithm.

Distance-vector (DV) algorithm — based on Bellman-Ford algorithm.

Graph model of a network — weighted directed graph.

Another day of class

Week 9.2 - Mar 02


This is going to be on the final. Know the algorithms.

Require the state (cost) of every link in the network. Centralized algorithm, though it’s possible to have every router run the algorithm, instead of having a single central router compute and distribute the information.

Based on Dijkstra’s algorithm. Dijkstra’s algorithm finds shortest paths from a fixed source node to every other node in the graph.

Each node u needs to compute the least cost path to every other node.


  • N = set of all nodes.

  • c(x,y) = cost of an edge xy

    • c(x,y) = infinity if there is no edge (aka x and y are not directly linked)

  • Let N' = set of nodes for all nodes v for which we have determined the shortest path from s to v.

    • Initially N' = {a}

  • s = source vertex

  • D[v] = Dist[v] = length of the shortest path from s to v for each v in N'

  • For each v not in N'

    • Dist[v] is length of an "estimated" shortest path from s to v

    • Initially, estimtated shortest paths are direct edges.

    • In general — these estimated shortest path from s to v are a sequence of vertices s = v1, v2, …​ , vk-1, vk = v.

      • Every vertex on the path except for the end vertex (the unknown vertex itself) is required to be in N'

  • For each v in N, we have P[v] = Pred[v], which is the predecessor of v along the shortest (estimated) path from s to v

Initialization (shortest paths from s to every other node):

N' = {s};
for each v in N {
    Dist[v] = c(s,v);
    Pred[v] = s;

We proceed in a series of n-1 steps. At each step, we add a new vertex v* to N'. We always select v* with minimum Dist[v] value, among all unknown vertices. If we do that, then the estimated shortest path to v* is actually a shortest path.

For any other path s to v*, let w be the first vertex not in N'. Then Dist[v*] ⇐ Dist[w], so the length of the path to v* is shorter than any other path s to v*.

N = N + {v*}. Add v* to N', and then adjust Dist[] and Pred[] values for all neighbors of v*.


loop n-1 times {
    let v* be outside of N' with minimum Dist[] value
    N' = N' + {v*}
    for each neighbor x of v* not in N' {
        if(Dist[v*] + c(v*, x) < Dist[x]) {
            Dist[x] = Dist[v*] + c(v*, x);
            Pred[x] = v*;

The forwarding table entry for a node destination y: (y, first hop along shortest path to y).


u - w = 5
u - v = 2
u - x = 1
x - v = 2
x - y = 1
x - w = 3
v - w = 3
w - y = 3
y - z = 2
w - z = 5

             Dist[x], Pred[x]
Step    N'       v       x       w        y       z
0       u       2,u     1,u     5,w     inf,u    inf,u
1       ux      2,u     1,u     4,x      2,x     inf,u

Load sensitive link state algorithms are susceptible to a problem called route oscillation.

Distance Vector Algorithm

A distributed algorithm that is run at each individual router. Each router needs information on reachability estimates from its neighbors.

Based on the Bellman-Ford algorithm.

At each node x in N, define distance vectors (arrays of estimated distances from that node to every other node) Dx (distance vector for the node x itself), and Dw for each neighbor w of x, where for any vector v in N, Dv = [dv(y) for each y in N] where dv(y) is the estimated shortest distance from v to y.


var Dx, Dw for each neighbor w
//Initialize your own Dx
for each y in N {
    Dx[y] = c(x,y)
// send your Dx to each neighbor
for each neighbor w {
    send Dx to w

Big idea:

Whenever you detect a change in the cost of a directly connected link, or receive an update from a neighbor, you update your own Dx and send a copy to every neighbor.

To update: dx(y) = min{ c(x,w) + dw(y)} for all neighbors. If w* is the neighbor that achieves the minimum, set (y, w*) in the forwarding table.

If Dx changes as a result, send it to every neighbor.

Another day of class

Week 10.1 - Mar 07


x - y = 2
x - z = 7
y - z = 1

Initialization phase:

Table 5. Table for node x:
















Table 6. Table for node y:
















Table 7. Table for node z:
















First iteration:

Table 8. Table for node x:






min{y: c(x,y) [2] + Dy(y) [0] = 2, z: c(x,z) [7] + Dz(y) [1] = 8} = 2

min{y: c(x,y) [2] + Dy(z) [1] = 3, z: c(x,z) [7] + Dz(z) [0] = 7} = 3









Table 9. Table for node y:









min{x: c(y,x) [2] + Dx(x) [0] = 3, z: c(y,z) [1] + Dz(x) [7] = 8} = 3


min{x: c(y,x) [2] + Dx(z) [7] = 9, z: c(y,z) [1] + Dz(z) [1] = 1} = 1





Table 10. Table for node z:













min{x: c(z,x) [7] + Dx(x) [0] = 7, y: c(z,y) [1] + Dy(x) [2] = 3} = 3

min{x: c(z,x) [7] + Dx(y) [2] = 9, y: c(z,y) [1] + Dy(y) [0] = 1} = 1


Internet IP address assignment

From 1981-1993

Internet used Classful addressing (class-based IP addresses). 5 classes of IP addresses: A, B, C, D, E.

Class A addresses: 8 bit network prefix, 24 bit host suffix. The leading bit in a Class A address is 0. This means it allows 27 (128) Class A networks worldwide, each having 224 computers. The first byte is from 0 to 127. Range of Class A IP addresses: -

Class B addresses: The leading bits are 10. 16 bit network prefix, 16 bit host suffix. 214 class B networks, each has 216 computers. Leading byte: 128..191. Range of Class B IP addresses: -

Class C addresses: The leading bits are 110. Class C has a 3 byte network prefix (24 bits) and an 8 bit host suffix. Can have 221 class C networks, and 255 computers on each network. Leading byte: 192..223. Range of Class C IP addresses: -

Class D addresses are reserved for multicast, and have a prefix of 1110. The range of class D addresses is to

Class E addresses are for experimental purposes, and have a prefix 1111. The range of class E addresses is -

Subnetting and CIDR

Subnetting and Classless Inter Domain Routing (CIDR) — invented to conserve IP addresses.

CIDR allows variable length network prefixes. To denote a network prefix, use the notation IP address/length of network prefix.

An IP subnet is a maximally connected collection of interfaces that does not include a router.

A forwarding table pairs (network prefix, interface). Use the 'longest matching prefix rule' to keep forwarding tables from exploding in size.

You're right. So much better.


chase-smith commented Jan 11, 2017

The specific variant I use (and the same one GitHub uses) is . User manual at ; quick reference

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment