# C代写 | CS 456/656 Spring Assignment 3

### C代写 | CS 456/656 Spring Assignment 3

C语言实现网络链路路由程序

Assignment 3
Computer Networks (CS 456/656)  Spring 20 19
Shortest Path Routing Algorithm
Due Date: Monday, July 29, 2019, before midnight (11:59 PM ) Work on this assignment is to be completed individually
1 Assignment Objective
For this assignment, you will implement a shortest path routing algorithm.( OSPF). 2 Overview
Like  most  link‐state  algorithms,  OSPF  uses  a  graph‐theoretic  model  of  network  topology  to  compute  shortest  paths.  Each  router  periodically  broadcasts  information  about  the  status  of  its  connections.  OSPF  floods  each  status  message  to  all  participating  routers.  A  router  uses  arriving  link  state  information to assemble a graph. Whenever a router receives information that changes its copy of the  topology  graph,  it  runs  a  conventional  graph  algorithm  to  compute  shortest  paths  in  the  graph,  and  uses the results to build a new next‐hop routing table.

FIGURE 1: INTERNET TOPOLOGY

OSPF  uses  a  directed  graph  to  model  an  Internet.  Each  node  in  an  OSPF  topology  graph  either  corresponds  to  a  router  or  a  network.  If  a  physical  connection  exists  between  two  objects  in  an  Internet,  the  OSPF  graph  contains  a  pair  of  directed  edges  (one  in  each  direction)  between  the  two  nodes  that  represent  the  objects.  To  enable  routers  to  compute  shortest  paths,  each  edge  in  an  OSPF  graph is assigned a weight that corresponds to the cost of using the path.

The  identities  of  the  links  that  are  attached  to  a  router  together  with  their  cost  metrics  are  entered  into a table (known as the circuit database).

1

2
Circuit Database for R1
Cost
L1  2  L2  1
FIGURE 2: INITIALIZED CIRCUIT DATABASE

Before a router can send any PDU to its neighbors it should first send a HELLO PDU to tell its neighbor  that  the  router  is  ready  to  participate  in  the  OSPF  procedure.  So  at  the  beginning  of  the  procedure  each router sends a HELLO PDU to each of its neighbors.

Each router sends to each of its neighbors a link state (LS) PDU containing the identifiers of the  links to which the router is attached together with the cost values. In this way, a router receives some  LS PDUs from each of its neighbors informing it of the links that are attached to it and their cost values.  This information is stored in the link state database by the update process in the router.

R1
From R2 – R2: L1,2/L3,4/L4,1/L6,4  R3 – R3: L2,1/L3,4/L5,3/L8,4
R2
From R1 – R1: L1,2/L1,1  R3 – R3: L2,1/L3,4/L5,3/L8,4  R4 – R4: L4,1/L5,3/L7,5  R5 – R5: L6,4/L9,2
|  |  |
R7
From R4 – R4: L4,1/L5,3/L7,5  R5 – R5: L6,4/L9,2  R6 – R6: L8,4/L10,2

FIGURE 3: LINK STATE DATABASE AFTER FIRST SET OF LS PDUS

When it has done this, the update process in each router sends a copy of the LS PDU to each of its  neighbors (except the one that has sent the PDU and those from which it has not received a HELLO PDU  yet;  also  the  same  message  should  be  sent  to  a  router  only  once  to  avoid  loops).  As  a  result,  each  router  receives  a  further  set  of  LS PDUs  which  have  effectively  originated  from  its  neighbors’  neighbors.  This  procedure  then  continues.  As  can  be  deduced,  over  a  period  of  time  each  router  will  receive a complete set of LS PDUs containing the identities of the links ‐ and their path cost values ‐  which are attached to all other routers in the Internet.

Whenever  a  new  set  of  LS PDUs  is  entered  into  the  link  state  database,  the  router  performs  the  Shortest  Path  First  (SPF)  algorithm  on  the  link  state  database,  and  determines,  from  all  the  entries  in

the  various  databases,  which  neighbor  R  should  be  used  to  reach  each  of  the  other  routers  based  on  their corresponding path cost values.

To illustrate this procedure, consider its application to the example subnet shown in Figure 1.

The initialized circuit database is shown in Figure 2 and the first set of LS PDUs that are received by  each router (R) is shown in Figure 3.

For example, R1 will receive 8 LS PDUs, 4 from R2 and 4 from R3. Similarly, R2 will receive 11 LS PDUs,  2 from R1, 4 from R3, 3 from R4 and 2 from R5.

As  described  earlier,  on  receipt  of  each  of  these  PDUs  and  if  those  later  affect  its  LS  database,  each  R  will then generate another set of LS PDUs, and pass them on to each of its neighbors. This procedure  then repeats. The first, second and third sets of LS PDUs that will be received by R1 are shown in Figure  4, Figure 5, and Figure 6.

3
FIGURE 4: LINK STATE DATABASE DEVELOPMENT FOR R1 (FIRST SET OF LS PDUS)

FIGURE 5: LINK STATE DATABASE DEVELOPMENT FOR R1 (SECOND SET OF LS PDUS)

FIGURE 6: LINK STATE DATABASE DEVELOPMENT FOR R1 (THIRD SET OF LS PDUS)

Finally,  Figure  7  shows  the  output  of  the  decision  process  for  R1.  This  is  the  routing  information  base  (RIB) and is computed by the decision process performing the SPF algorithm on the contents of the link
state database to determine the shortest (minimum) path cost to each destination R.
Destination R
Path, Cost
R1  R2  R3  R4  R5  R6  R7
Local,0  R2,2  R3 1  R2,3  R2,6  R3,5  R3,7
FIGURE 7: FINAL RIB FOR R1
3 Hints
The following structures are assumed (and should be respected):
#define NBR_ROUTER 5
struct pkt_HELLO
{
unsigned int router_id;
strruct pkt_LSPDU
{
unsigned int sender;
unsigned int router_id;
unsigned int cost;
unsigned int via;
/* for simplicity we consider only 5 routers */
/* id of the router who sends the HELLO PDU */
/* id of the link through which it is sent */
/* sender of the LS PDU */
/* router id */
/* link id */
/* cost of the link */
/* id of the link through which the LS PDU is sent */
}
}

4

struct pkt_INIT
{
unsigned int router_id;
{
unsigned int cost;
struct circuit_DB
{
/* we assume that at most NBR_ROUTER links are attached to each router */
}
When a router needs to send packets to another router, it sends them to the Network State Emulator  instead of sending them directly to the router. The Network State Emulator then forwards the routers  packets to the right receiver.
4 What to do?
You should implement the router program, named router. Its command line input should include the  following:

where ,
• <router_id> is an integer that represents the router id. It should be unique for each router.  • <nse_host> is the host where the Network State Emulator is running.
• <nse_port> is the port number of the Network State Emulator.
• <router_port> is the router port

You  will  be  given  the  executable  of  the  Network  State  Emulator  (nse),  where  circuit  databases  are
hardcoded and will be sent to the routers during the initialization phase. Its command line is:

where,
• <routers_host> is the host where the routers are running. For simplicity we suppose that all
routers are running on the same host.
• <nse_port> is the Network State Emulator port number.

The  Network  State  Emulator  will  not  affect  any  packet;  it  simply  forwards  the  packet  to  the  right  receiver. The topology used by the simulator is also provided in an accompanying PDF file.
First each router must send an INIT packet to the Network State Emulator containing the router’s id.  After  the  Network  State  Emulator  receives  an  INIT  packet  from  each  router,  the  Network  State  Emulator will send to each router the circuit database associated with that router. The circuit database
}
/* id of the router that send the INIT PDU */
/* link id */
/* associated cost */
}

5
nse <routers_host> <nse_port>
/* number of links attached to a router */
router <router_id> <nse_host> <nse_port> <router_port>

will  be  sent  in  a  circuit_DB  structure.  For  the  assignment,  you  should  always  run  the  five  router  programs in order from the 1st to the 5th.
Then each router must send a HELLO packet to all its neighbors. Each router will respond to each HELLO  packet by a set of LS PDUs containing its circuit database. When receiving an LS PDU a router will  update its topology database and then it will send to all its neighbors (except the one that send the LS PDU and those from which the router did not receive a HELLO packet yet) the LS PDU. The LS PDU is  contained  in  the  pkt_LSPDU  structure.  Before  a  router  can  send  the  pkt_LSPDU,  it  must  change  the  field  sender  to  its  router  id  value.  When  receiving  an  LS PDU  a  router  should  also  use  the  Dijkstra  algorithm  using  its  link  state  database  to  determine  the  shortest  (minimum)  path  cost  to  each  destination R.

For  both  testing  and  grading  purpose,  your  router  program  should  be  able  to  generate  a  log  file,  named as router (id).log, where id is the id of the router (i.e. router 1 will generate a log file with  name  router1.log).  The  routers  must  record  in  the  log  file  all  the  messages  that  they  receive  and  all  messages that they send. They must also record their topology database every time this later changes.  The  log  file  should  contain  the  corresponding  RIB  for  each  topology.  Before  each  line  of  the  trace,  the  router must write its id.

An example of a message trace is the following:

R1 receives an LS PDU: sender 3, router_id 7, link_id 7, cost 5, via 2  /* it can be interpreted as : R1 receives from R3 via link id 2 that R7 has a link with id 7 and cost 5 */

An example of a topology database is shown in the following:  # Topology database
R1 -> R1 nbr link 2
R1 -> R1 link 1 cost 2
R1 -> R1 link 2 cost 1
R1 -> R2 nbr link 4
R1 -> R2 link 1 cost 2
R1 -> R2 link 3 cost 4
R1 -> R2 link 4 cost 1
R1 -> R2 link 6 cost 4
Notice that the topology database will be subject to change every time information about a new router  becomes available

An example of a RIB is given below:  # RIB
R1 -> R1 -> Local, 0
R1 -> R2 -> R2, 2
R1 -> R3 -> R3, 1
R1 -> R4 -> R2, 3
R1 -> R5 -> R2, 6
R1 -> R6 -> R3, 5
R1 -> R7 -> R3, 7

6

4.1 Example Execution (with 5 routers)
• On the host hostX
nse hostY 9999

• On the host hostY
router 1 hostX 9999 9991
router 2 hostX 9999 9992 router 3 hostX 9999 9993 router 4 hostX 9999 9994 router 5 hostX 9999 9995
• Expected output
router1.log router2.log router3.log
router4.log router5.log
5 Procedures
5.1 Due Date
Monday, July 29, 2019, before midnight (11:59 PM)
5.2 Hand in Instructions

Submit your all your files in a single compressed file (.zip, .tar etc.) using UW‐LEARN Assignment 3 Drop  Box.

You must hand in the following files / documents:
• Source code files.
• Makefile: your code must compile and link cleanly by typing “make” or “gmake”.
• README  file:  this  file  must  contain  instructions  on  how  to  run  your  program,  which  undergrad
machines  your  program  was  built  and  tested  on,  and  what  version  of  make  and  compilers  you
are using.
If you choose not to use C, the makefile you submit must generate shell scripts that run your programs  as specified. Name the script router.

Your implementation will be tested on the machines available in the undergrad environment.
5.3 Documentation
Since  there  is  no  external  documentation  required  for  this  assignment,  you  are  expected  to  have  a  reasonable amount of internal code documentation (to help the markers read your code).

You will lose marks if your code is unreadable, sloppy, inefficient, or not modular.
5.4 Evaluation
Work on this assignment is to be completed individually.

7