Static routing代做、代写algorithm留学生、代写R设计、代做R编程语言

日期：2019-06-12 10:42

第三组

part 1 Static routing

Static routing is a type of routing algorithm that makes use of manually configured routing

table entries, in contrast to dynamic routing algorithms which use network messages to determine

the best routes. When failures happen in the network, static routes will not get updated. They

have to be manually updated to use a different route. This already highlight one of the drawbacks

of static routing schemes.

Advantages:

- Little resource usage

- Secure (Administrators have a lot of control over the routing)

- Great for small networks (less complexity)

Disadvantages:

- Human errors

- Fault tolerance

For more information see section 5.6.2 of the book.

Routing tables

A router uses its routing table to decide where to forward incoming packets. A typical routing

table may contain the following columns:

- Network destination: The range of destination IPs that can be reached on this network.

- Subnet mask: This separates the destination IP into its network address and host address

components.

- Gateway: The IP address of the next router to which to send the packet.

When the router receives a packet, it checks which network destination(s) correspond(s) to the

packet’s destination address. (If there are multiple network destinations possible, the one with the

longest prefix match is preferred.) It then forwards the packet to the appropriate gateway.

Programming exercise

In this programming exercise, you will implement a static routing table. A template will be

provided with the correct function signatures. A basic test case can be found under the Test tab,

but you are highly encouraged to write your own test cases to make sure your implementation is

correct.

You are given two functions (exact method signatures can be found in the code template):

Add Route (Network Prefix: int, Subnet Mask: int, Gateway: int) -> void

This function is used to add route entries to your static routing table.

Arguments:

- Network prefix: Network address of the subnet.

- Subnet Mask: Mask corresponding to the subnet.

- Gateway: Router that can handle traffic belonging to the subnet.

All arguments use the same format: an ip address in the form of a 32-bit binary sequence. We

provide a function for you in the Library to convert from a decimal IP address representation to a

binary one.

"255.255.0.0": str -> 11111111 11111111 00000000 00000000: int

We use this function in our tests to add entries to your routing table.

Returns: This function should not return anything

Lookup Route (Address: int) -> int

This function is used to lookup the route for a specific IP address.

Arguments:

- Address: The IP address that we want to route to.

All arguments use the same format: an ip address in the form of a 32-bit binary sequence. We

provide a function for you in the Library to convert from a decimal IP address representation to a

binary one.

"255.255.0.0": str -> 11111111 11111111 00000000 00000000: int

We use this function in our tests to check if your routing logic is correct.

Returns: This function should return the gateway of the matched route as a binary sequence. If

no valid route can be found the function should return ERROR_NO_ROUTE, which is mapped to

-1 in the code.

Assumptions

You can assume that our input is valid and non-malicious.

You can assume that the routing table does not change after the intial filling.

part 2 Dynamic Routing - Distance Vector

Dynamic routing makes use of messages to learn where to route packets to get them to their

destination. There are two different types of dynamic routing algorithms: Distance Vector and Link

State. Distance vector routing algorithms only gather data from their neighbour (directly

connected) routers, while link state gathers data from all routers in the network. Because of this

difference both types of algorithms have different advantages and disadvantages.

Distance Vector

Distance vector algorithms only know the state of their neighbours. They use propagation to

spread knowledge about distant routers. Each router slowly learns more about the network by

gossiping newly discovered routers.

Advantages compared to link state algorithms:

- Low bandwidth requirements due to local sharing

- Small packets

- No flooding

Disadvantages compared to link state algorithms:

- Based on local knowlegde instead of global

- Converges slowly e.g. takes longer to propegate broken links

An example of a distance vector algorithm is RIP.

Programming exercise

In this programming exercise, you will implement a distance vector routing table. A template will

be provided with the correct function signatures. A basic test case can be found under

the Testtab, but you are highly encouraged to write your own test cases to make sure your

implementation is correct.

You are given the following functions (exact method signatures can be found in the code

template):

Constructor (Router Identifier: str) -> void

This function is used to store the router indentifier.

Arguments:

- Router Identifier: Name of the router. This argument is a 4 character hexadecimal string.

Returns: This function should not return anything

Process Packet (Packet: str) -> str

This function is given to parse the raw packet and detect the type of packet and subsequently call

the corresponding function .e.g Process Data Packet or Process Routing Packet. We provide this

function because learning how to parse strings is not an objective of this course. You shouldn’t

have to touch or understand this function to complete the assignment.

Arguments:

- Packet: Incoming network packet. The format of the packet is specified below.

Network packet format: (For explanation only)

D <source> <destination> <message>

Where:

- Source: The original source of the packet. (4 character hexadecimal string)

- Destination: The destination of the packet. (4 character hexadecimal string)

- Message: The actual message. (arbitrary length hexadecimal string)

R <identifier> <latency> <n> <identifier-n> <latency-n> ...

Where:

- identifier: The identifier of the neighbour router. (4 character hexadecimal string)

- latency: The network latency to the neighbour router measured from your router. (number)

- n: The number of route entries in the neighbours routing table. (number)

- identifier-n: The identifier of the router in the routing table. (4 character hexadecimal string)

- latency-n: The latency of the router in the routing table measured from the neighbour router.

(number)

Examples of valid packets are:

D aaaa bbbb 1234567890abcdef

R cccc 20 2 bbbb 5 2222 25

Returns: This function should return the output from either the Process Data Packet function or

the Process Routing Packet function. If an invalid type is provided the function should return

ERROR_INVALID_TYPE, which is mapped to ‘INVALID TYPE’ in the code.

Process Data Packet (Source: str, Destination: str, Message: str) -> str

This function processes data packets and looks up the route and latency in the routing table(s)

and returns these. If a message is directed to the current router, the router should return

MESSAGE_THANK_YOU, which is mapped to ‘THANK YOU’ in the code.

Arguments:

- Source: Original source of message. This argument is a 4 character hexadecimal string.

- Destination: Final destination of message. This argument is a 4 character hexadecimal string.

- Message: Fake message.

Returns: This function should return the neighbour router which can route to the desired

destination and the total latency to the final destination (format provided below). If no valid route

can be found the function should return ERROR_NO_ROUTE, which is mapped to ‘NO ROUTE’ in

the code. If a message is directed to the current router, the router should return

MESSAGE_THANK_YOU, which is mapped to ‘THANK YOU’ in the code.

<identifier> <total latency>

cccc 25

Process Routing Packet (Router Identifier: str, Latency: int, Routes: List[Route]) -> str

This function processes routing packets and updates the routing table(s) with new information.

Arguments:

- Router Identifier: Name of the neighbour router. This argument is a 4 character hexadecimal

string.

- Latency: The network latency to the neighbour router measured from your router.

- Routes: List of routes from the neighbour router.

Route (Router Identifier: str, Latency: int)

Where:

- Router Identifier: The identifier of the router in the routing table of your neighbour. This

argument is a 4 character hexadecimal string.

- Latency: The latency of the router in the routing table of your neighbour measured from the

neighbour router.

Returns: This function should return MESSAGE_ROUTE_RECEIVED (which is mapped to

‘RECEIVED’ in the code) for every routing packet received

Pointers

If two routes have the same total latency return the one which is the newest.

Routers can update their latency or the latency of their neighbours. Since this makes the

exercise more complex, we have designed the spec tests in such a way that it is possible to

pass the assignment (score 90/100) without having this functionality. If you do want to go

for the full 100/100, here are some hints for different datastructures that can be used:

Less efficient, but easier (work is done on Data Packet instead of Routing Packet)

Map[Destination: str, Map[Forwarding Router: str, Latency: int]] (Routes table)

Map[Forwarding Router: str, Latency: int] (Neighbours table)

More efficient, but harder (work is done on Routing Packet instead of Data Packet)

Map[Destination: str, Route (Forwarding Router: str, Total latency: int)] (Routing table lookup)

Map[Destination: str, Map[Forwarding Router: str, Latency: int]] (Routes table)

Map[Forwarding Router: str, Latency: int] (Neighbours table)

Assumptions

You can assume that our input is valid and non-malicious.

since you don’t have a view of the entire network.

You can assume the latency is the same in both directions

Part 3 Dynamic Routing - Link State

Dynamic routing makes use of messages to learn where to route packets to get them to their

destination. There are two different types of dynamic routing algorithms: Distance Vector and Link

State. Distance vector routing algorithms only gather data from their neighbour (directly

connected) routers, while link state algorithms gather data from all routers in the network.

Because of this difference both types of algorithms have different advantages and disadvantages.

Link State

Link state algorithms work on global state. Every router gathers information about its neighbours

and floods this through the network. This approach leads to a very fast converging time, but also

creates network overhead.

An example of a distance vector algorithm is OSPF.

Programming exercise

In this programming exercise, you will implement a link state routing table. A template will be

provided with the correct function signatures. A basic test case can be found under the Test tab,

but you are highly encouraged to write your own test cases to make sure your implementation is

correct.

You are given four functions (exact method signatures can be found in the code template):

Constructor (Router Identifier: str, Neighbours: Map[Neighbour Identifier: str, latency: int]) -> void

This function is used to store the router identifier.

Arguments:

- Router Identifier: Name of the router. This argument is a 4 character hexadecimal string.

- Neighbours: Map of directly connected neighbours

Returns: This function should not return anything

Process Packet (Packet: str) -> str

This function is given to parse the raw packet and detect the type of packet and subsequently call

the corresponding function, .e.g Process Data Packet or Process Routing Packet. We provide this

function because learning how to parse strings is not an objective of this course. You do not have

to touch or understand this function to complete the assignment.

Arguments:

- Packet: Incoming network packet. The format of the packet is specified below.

Returns: This function should return the output from either the Process Data Packet function or

the Process Routing Packet function. If an invalid type is provided the function should return

ERROR_INVALID_TYPE, which is mapped to ‘INVALID TYPE’ in the code.

Network packet format: (For explanation only)

D <source> <destination> <message>

Where:

- Source: The original source of the packet. (4 character hexadecimal string)

- Destination: The destination of the packet. (4 character hexadecimal string)

- Message: The actual message. (arbitrary length hexadecimal string)

Example of a valid data packet is:

D aaaa bbbb 1234567890abcdef

R <identifier> <n> <identifier-1> <latency-1> ... <identifier-n> <latency-n>

Where:

- identifier: The identifier of the neighbour router. (4 character hexadecimal string)

- n: The number of route entries in the neighbours routing table. (number)

- identifier-i: The identifier of the i-th router in the routing table, where i is a number between 1 to

n (inclusive). (4 character hexadecimal string)

- latency-i: The latency of the i-th router in the routing table measured from the neighbour router,

where i is a number between 1 to n (inclusive). (number)

Example of a valid routing packet is:

R cccc 2 bbbb 5 2222 25

Process Data Packet (Source: str, Destination: str, Message: str) -> str

This function processes data packets and looks up the route and latency in the routing table(s)

and returns these. If a message is directed to the current router, the router should

return MESSAGE_THANK_YOU, which is mapped to THANK YOU in the code.

Arguments:

- Source: Original source of message. This argument is a 4 character hexadecimal string.

- Destination: Final destination of message. This argument is a 4 character hexadecimal string.

- Message: Fake message.

Returns: This function should return the neighbour router which can route to the desired

destination and the total latency to the final destination (format provided below). If no valid route

can be found the function should return ERROR_NO_ROUTE, which is mapped to NO ROUTE in

the code. If a message is directed to the current router, the router should

return MESSAGE_THANK_YOU, which is mapped to THANK YOU in the code.

note: If 2 routes are equal it should pick the one that has been most recently updated.

Example of such a return message is:

<identifier> <total latency>

cccc 25

Process Routing Packet (Router Identifier: str, Latency: int, Routes: List[Route]) -> str

This function processes routing packets and updates the routing table(s) with new information.

Arguments:

- Router Identifier: Name of the neighbour router. This argument is a 4 character hexadecimal

string.

- Latency: The network latency to the neighbour router measured from your router.

- Routes: List of routes from the neighbour router.

Route (Router Identifier: str, Latency: int)

Where:

- Router Identifier: The identifier of the router in the routing table of your neighbour. This

argument is a 4 character hexadecimal string.

- Latency: The latency of the router in the routing table of your neighbour measured from the

neighbour router.

Returns: This function should return MESSAGE_ROUTE_RECEIVED (which is mapped to

‘RECEIVED’ in the code) for every routing packet received

Assumptions

You can assume that our input is valid and non-malicious.

You can assume that the network graph stays static, but new nodes can still be discovered,

since you don’t have a view of the entire network from the beginning.

You can assume the latency is the same in both directions