COMP9332 Network Routing and Switching
(1) Semester 1, 2018, Due: 23:59, 3 Jun 2018 (Wek 13), Weighting: 25%. Note
that this is a hard deadline. No late submision wil be alowed.
(2) There are a total of 5 tasks with varying weights. Al tasks must be
attempted.
(3) Answers must be submited electronicaly via give. The only format acepted
is Acrobat pdf. The recomended file name is your student number. The
submission comand (assuming your student number is 1234567) is:
give cs9332 assignment 1234567.pdf
Analysis of Geographic Routing Algorithms
Introduction
Geographic routing is very diferent 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 wireles communications. Week 8 lecture explains thre diferent routing
algorithms used in geographic routing. The purpose of this asignment 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
Discusion Forum (in Modle). The Lecturer wil then adres any major isues
in a revised version.
Learning Objectives
By completing this asignment, students wil
• Learn geographic routing algorithms in more details.
• Gain experience in analysing new forms of routing that could be
significantly diferent 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 droped by Random Progres 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 Progres 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 Progres could deliver it.
(5) [40 marks] Existing geographic routing algorithms are based on single-
hop 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 single-
hop algorithms using carefuly designed topologies. You need to first
identify a list of benefits (diferent algorithms may benefit diferently
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 asignment. Your submision wil be checked by plagiarism
software against other submissions. There are strict penalties for plagiarism. Se
course overview for plagiarism policy.