Lesson 5 - Router Design and Algorithms (part 1)

Question 1

What are the general components of a router

Answer 1

input/output ports,
the switching fabric
routing processor.

Question 2

What functions do the router’s input ports provide?

Answer 2

1. Physically terminate the incoming links.
2. Decapsulate the packets.
   3 Perform the lookup function.

Question 3

What does the switching fabric of the router do?

Answer 3

moves the packet from the input to output ports.

Question 4

Name the three types of switching fabrics in a router.

Answer 4

1. Memory
2. Bus
3. Crossbar

Question 5

What is the function of a routers output ports?

Answer 5

receive and queue packets from the switching fabric and send them over to the outgoing link.

Question 6

Describe the router Lookup task

Answer 6

When a packet arrives at the input link, the router looks at the destination IP address and determines the output link by looking at the forwarding table

Question 7

What are the major tasks of a router?

Answer 7

1. Lookup
2. Switching
3. Queuing
4. Header Validation & checksum
   5 Route processing
5. Protocol Processing

Question 8

Describe how a switching via memory is accomplished.

Answer 8

When an input port receives a packet, it sends an interrupt to the routing processor and the packet is copied to the processor’s memory. Then the processor extracts the destination address and looks into the forward table to find the output port, and finally the packet is copied into that output’s port buffer.

Question 9

Describe how a switching via bus is accomplished.

Answer 9

When an input port receives a new packet, it puts an internal header that designates the output port, and it sends the packet to the shared bus. Then all the output ports will receive the packet, but only the designated one will keep it. When the packet arrives at the designated output port, then the internal header is removed from the packet. Only one packet can cross the bus at a given time, and so the speed of the bus limits the speed of the router.

Question 10

Describe how a switching via interconnection network is accomplished.

Answer 10

A crossbar switch is an interconnection network that connects N input ports to N output ports using 2N buses. Horizontal buses meet the vertical buses at crosspoints which are controlled by the switching fabric. For example, let’s suppose that a packet arrives at port A that will need to be forwarded to output port Y, the switching fabric closes the crosspoint where the two buses intersect, so that port A can send the packets onto the bus and then the packet can only be picked up by output port Y. Crossbar network can carry multiple packets at the same time, as long as they are using different input and output ports.

Question 11

What are the bottlenecks routers face?

L5, Challenges that the router faces

Answer 11

1. Exact look-ups
2. prefix look-ups
3. Packet classification
4. Switching
5. Fair queueing
6. Internal bandwidth
7. Measurement
8. Security

Question 12

What is prefix-match lookup?

Answer 12

A router look-up table “groups” multiple IP addresses by the same prefix.

Question 13

What are the 2 main problems of the routers? Explain, what causes these problems.

Answer 13

1. Bandwidth and Internet population scaling: These scaling issues are caused by: a) An increasing number of devices that connect to the Internet, 2) Increasing volumes of network traffic due to new applications, and 3) New technologies such as optical links that can accommodate higher volumes of traffic.
2. Services at high speeds: New applications require services such as protection against delays in presence of congestion, and protection during attacks or failures. But offering these services at very high speeds is a challenge for routers.

Question 14

What are the ways to denote a prefix?

Answer 14

1. Dot decimal 132.234
2. Slash notation 132.238.9.0/16
3. Masking (ex 225.255.00 denotes 16 bits)

Question 15

What is CIDR? Why was it introduced?

Answer 15

Classless Internet Domain Routing.

CIDR has helped to decrease the router table size

Question 16

Name 4 takeaway observations around network traffic characteristics. Explain their consequences.

Answer 16

1. network traffic had shown a large number of concurrent flows of short duration. This has a consequence that a caching solution would not work efficiently.
2. The important element while performing any lookup operation is how fast it is done (lookup speed). A large part of the cost of computation for lookup is accessing memory.
3. An unstable routing protocol may adversely impact the update time in the table: add, delete or replace a prefix. Inefficient routing protocols increase this value up to additional milliseconds.
4. An important tradeoff is memory usage; we have the option to use expensive fast memory (cache in software, SRAM in hardware) or cheaper but slower memory (e.g., DRAM, SDRAM).

Question 17

Why do we need multibit tries?

Answer 17

unibit tries require many memory lookups which can take a long time for high speed links.

Question 18

What is prefix expansion and why is it needed?

Answer 18

prefix expansion expands a given prefix to more prefixes. This strategy ensures that the expanded prefix is a multiple of the chosen stride length. Prefixes that are not a multiple of the stride length are removed.

For example we expand 11001* with 110010* and 110011*.

Why? The expansion gives us more speed with an increased cost of the database size.

Question 19

How does fixed stride prefix-match lookup work.

Answer 19

1. Every element in a trie represents two pieces of information: a pointer and a prefix value.
2. The prefix search moves ahead with the preset length in n-bits (3 in this case)
3. When the path is traced by a pointer, we remember the last matched prefix (if any).
4. Our search ends when an empty pointer is met. At that time, we return the last matched prefix as our final prefix match.

Question 20

What are the benefits of variable stride vs fixed stride

Answer 20

tries don’t have to contain the same number of bits (or strides)
Therefore, by varying the strides we could make the our prefix database smaller, and optimize for memory.