A walkthrough
Computer Science Tutoring
• Emulate a link layer and a network layer protocol
• 2 Independent Sections
–Go Back N (link layer)
–Distance Vector Protocol (network layer)
•Will combine the 2 sections such that both algorithms working in tandem
• Implement the Go-Back-N (GBN) protocol on top of UDP to guarantee that all packets can be successfully delivered to the higher layers in the correct order
• To emulate an unreliable channel, the receiver and the sender need to drop an incoming data packet or an ACK, respectively, with a certain probability
Go Back-N: Details
• One program “gbnnode”
• Two node instances, sender and receiver
• Both node processes will be on the same machine but
different port numbers
• Data packet: 1 character
• Loss emulation: probabilistic or deterministic
Go Back-N: Setup Two nodes, sender and receiver
Go Back-N: Loss Rate Calculation
After transmission, sender and receiver each report:
Loss rate = # packets dropped / total # packets
A test: In probabilistic mode, actual loss rate should converge to command line drop probability p
Distance Vector Protocol
• Objective: Implement a simplified version of a routing
protocol in a static network.
• Use the Bellman-Ford algorithm to build and update the
routing tables
• UDP should be used to exchange the routing table information among the nodes
• We assume that that all the nodes run on the same machine and they all have the same IP address
• Each node can be identified uniquely by a (UDP listening) port number, which is specified by the user
Keeping track of Routing Table
• Upontheactivationoftheprogram,eachnodeshould construct the initial routing table and keep it locally
• Thenodewiththelastkeywordwillsendoutitsrouting table first
• UsingBellman-Ford,eachnodewillkeepupdatingits routing table as long as neighboring nodes send their updated routing tables information
• Ifthereisanychangeintheroutingtable,anodeshould send the updated information to its neighbors.
• NOTE:Eachnodeshouldsenditsroutingtableinformation to its neighbors at least once.
Initializing Network Topology
Status Messages!
• Make sure to follow the status messages specified (Don’t do anything fancy please)
Please note all the assumptions in this section
• Max Nodes = 16
• Links and distances (costs) specified at start
and stay static throughout test
• Distance is same in both directions
• Use UDP (if you did PA1 then you already know how!)
Combination
• GBN part + DV routing part to emulate a computer network with dynamic link state
• Goal is to integrate code you’ve already written.
Dynamic Links
• Use code from GBN section
• Probe packets instead of char messages
• Loss rate calc: simplified –Only probabilistic packet drop –ACKs never dropped –Window size == 5
Probe packets
• Probe packets sent continuously, loss rate updated
• Each link connects two nodes, specify sender node and receiver node
• Probe packets sent in one direction –Senders only get Link loss rate when receiver
sends over Routing Table update
Programming Help, Add QQ: 749389476
$ ./cnnode 1111 receive send 2222 3333 (receiving list is empty)
$ ./cnnode 2222 receive 1111 .1 send 3333 4444
$ ./cnnode 3333 receive 1111 .5 2222 .2 send 4444
$ ./cnnode 4444 receive 2222 .8 3333 .5 send last (sending list is empty)
Simple Example
Simple Example
• We will be running your code on Google Cloud Machines using Ubuntu 14.04 LTS
• Please run and test your code in this environment
• Java, Python, and C allowed (same rules as PA1)
– We will only be using Java 7 and JDK 1.7 (Not Java 8)
• Startearly
• Make sure a step works before going on to the next one
• When we ask for command line arguments we actually mean command line arguments
• Don’tsubmitclassorexecutablefiles
• Don’tsubmityoureclipsepackagestructure
• Java does not need a Makefile as long as the readme specified the main class
CS Help, Email: tutorcs@163.com
Notes from PA1
• Please submit .zip archives
• Remove logging / debugging print statements
in final submission
• Submit README as text file