代写 Network Routing and Switching

日期：2018-05-17 06:41

Individual Assignment

COMP9332 Network Routing and Switching

(1) Semester 1, 2018, Due: 23:59, 3 Jun 2018 (Week 13), Weighting: 25%. Note

that this is a hard deadline. No late submission will be allowed.

(2) There are a total of 5 tasks with varying weights. All tasks must be

attempted.

(3) Answers must be submitted electronically via give. The only format accepted

is Acrobat pdf. The recommended file name is your student number. The

submission command (assuming your student number is 1234567) is:

give cs9332 assignment 1234567.pdf

Analysis of Geographic Routing Algorithms

Introduction

Geographic routing is very different from the conventional table-driven routing

algorithms and protocols, such as RIP, OSPF and BGP. In geographic routing,

hosts are mobile devices that also act as routers to forward packets to each other

using wireless communications. Week 8 lecture explains three different routing

algorithms used in geographic routing.  The purpose of this assignment is to

analyse these algorithms in more details and propose some extensions to

improve their performance.

It is expected that students will discuss any confusions or issues in the

Discussion Forum (in Moodle). The Lecturer will then address any major issues

in a revised version.

Learning Objectives

By completing this assignment, students will

• Learn geographic routing algorithms in more details.

• Gain experience in analysing new forms of routing that could be

significantly different than the mainstream routing protocols.

• Develop abilities to scrutinise important properties of routing from the

algorithmic descriptions of the protocols.

TASKs:

(1)[15 marks] Using a carefully designed topology, show a situation when a

packet is dropped by Random Progress algorithm despite a routing path

existing to the destination

(2)[15 marks] Using a carefully designed topology, show a situation when a

packet using Random Progress algorithm travels a `non-shortest’ path.

Feel free to use your own definition of shortest path. It could be shortest

in the sense of geographical distance, or in terms of number of hops.

(3)[15 marks] Using a carefully designed topology, show a situation when

Most Forward Within Radius would create a routing loop.

(4)[15 marks] Using a carefully designed topology, show a situation when

Greedy Forwarding (void traversal not implemented) would fail to deliver

a packet, but Random Progress could deliver it.

(5)[40 marks] Existing geographic routing algorithms are based on singlehop

neighbour location information, which provides low complexity, but

is not optimal. In this task, you will consider an extension that allows

nodes to exchange their own positions as well as their one hop neighbour

information (exchange their ‘neighbour position tables’).

(a) Propose extensions of the three progress-based geographic routing

algorithms that select next hop based on two hop progress, i.e., the

progress is now calculated after the packet travels two hops instead of one

hop used by existing algorithms. You may use pseudo-code to specify the

algorithms.

(b) Show the benefits of the extended versions compared to the singlehop

algorithms using carefully designed topologies. You need to first

identify a list of benefits (different algorithms may benefit differently

from this extension) that are gained by extending the algorithms to 2-hop,

and then show each of these benefits using carefully chosen routing

scenarios.

Plagiarism

This is an individual assignment. Your submission will be checked by plagiarism

software against other submissions. There are strict penalties for plagiarism. See

course overview for plagiarism policy.