Lesson 5.1 - Router Design Basics

Question 1

Router used at GT network border b/w GT and rest of internet

Answer 1

M320

Question 2

Line cards

Answer 2

• Go into chassis
• Look kind of like network interface cards but ports are special (ports terminate in high-capacity fiber links instead of Ethernet, much larger)
• Basic I/O component of a router architecture
• Interface by which a router sends/receives data
• Each has a lookup table copy, capability to modify headers, and a queue (or buffer) for packets as they enter and leave the line card
• Many line cards in a router. Packet must traverse interconnection fabric to be sent to the appropriate output port

Question 3

Need for big fast routers

Answer 3

• Links are getting faster
• Traffic demands are increasing, particularly with rise of demanding apps like streaming video
• Networks are getting bigger in terms of # of hosts, routers, users
• There’s a perennial need, particularly in internet backbone networks

Question 4

Basic router architecture/function

Answer 4

1. Receives packet
2. Looks at packet header to determine destination
3. Looks in forwarding table to determine appropriate output interface
4. Modifies the packet header, such as decrementing the time to live (TTL) field and updating the IP header checksum appropriately
5. Sends packet to appropriate output interface

Question 5

Why does each network card have its own copy of forwarding table?

Answer 5

• Important design decision of modern routers
• Introduces complications but prevents a central table from becoming a bottleneck at high speeds
• Early router architectures did NOT do this. As a result, cards used shared buffer memory over a shared bus. Shared bus introduces a bottleneck and contention between diff cards that may all be performing lookups to the same shared memory
• Important innovation was to eliminate the shared bus and place lookup tables on individual line cards

Question 6

Design of the interconnect

Answer 6

• Another important design decision
• How the line cards should be connected to one another
• One possibility is shared bus, but disadvantage is it can only be used by one input/output combination in any single time slot

Question 7

Crossbar switch

Answer 7

• Enable input/output pairs that don’t compete to send traffic from input to output during same time slot
• AKA switched backplane
• Every input port has a connection to every output port
• During each time slot, each input is connected to 0 or 1 outputs

Question 8

Advantage of crossbar switching

Answer 8

Can exploit parallelism, by allowing multiple packets to be forwarded across the interconnect in parallel

Question 9

Maximal matching

Answer 9

-Want to achieve 1-to-1 mapping (a matching) in each time slot

Question 10

Speedup

Answer 10

Most router crossbars have this notion, whereby multiple matchings can be performed in the same time slot

Question 11

It’s common practice to run the interconnect at…

Answer 11

a higher speed than the input and output ports. e.g. if the line cards are running at 10 Gbps, then running the interconnect twice as fast would allow matchings to occur twice as fast as packets would arrive on the inputs or be forwarded to the outputs
-Doesn’t solve all problems, though. For example, if there’s only a single queue of packets at an input port, packets can be blocked behind packets that are destined for other output ports.

Question 12

Virtual output queues

Answer 12

Instead of 1 queue in the input, have 1 queue per output port. Helps cope with “head of line blocking”.

Question 13

2 important goals of scheduling

Answer 13

(scheduling is decision about which ports should be matched to which output ports during which time slots)

1. Efficiency: if there’s traffic at inputs destined for certain output ports, crossbar switch should schedule inputs and outputs so that traffic isn’t sitting idle at input ports if some traffic could be sent to available output ports
2. Fairness: Given demands at inputs, want to make sure each queue at input is scheduled fairly for some definition of fairness
   - Defining fairness is tricky. There are multiple possible definitions. We’ll look at an important one called Max Min Fairness.

Question 14

Max-Min Fairness

Answer 14

An allocation is max-min fair if we can’t make one of the flow rates better off without making some other rate worse off that’s already worse than the flow rate xi
-Results in small demands getting exactly what they ask for, and larger demands splitting remaining capacity amongst themselves equally

Question 15

Formal procedure of max-min fairness

Answer 15

1. Allocate resources to users in order of increasing demand
2. No user receives more than what they requested
3. Users that still have unsatisfied demands split the remaining resources

Question 16

Why is it called max-min fairness

Answer 16

It maximizes the minimum share to each user whose demand is not fully serviced

Question 17

How to achieve max-min fairness (3 approaches)

Answer 17

• Round-robin scheduling
• Bit-by-bit scheduling
• Fair queueing

Question 18

Round-robin scheduling

Answer 18

Given a set of queues, router services them in order. Problem here is that packets can have diff sizes. Servicing in order isn’t fair because first queue with bigger packet would get more than its fair share because packet just happened to be bigger

Question 19

Bit-by-bit scheduling

Answer 19

During each time slot, each queue has only 1 bit serviced.

-It is perfectly fair, but the problem is feasibility. How do we service 1 bit from a queue?

Question 20

Fair queueing

Answer 20

• Achieves max-min fairness by servicing packets according to the “soonest finishing time”
• Algorithm computes the virtual finishing time of all candidate packets, which are the packets at the head of all non-empty flow queues. Based on these virtual finishing times, fair queueing compares finishing times of each queue and services the queue with the minimum finishing time. So, the queue with the minimum virtual finishing time is serviced.