Lesson 5.1 - Router Design Basics Flashcards Preview

CS6250 - Networking > Lesson 5.1 - Router Design Basics > Flashcards

Flashcards in Lesson 5.1 - Router Design Basics Deck (20)
Loading flashcards...
1
Q

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

A

M320

2
Q

Line cards

A
  • 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
3
Q

Need for big fast routers

A
  • 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
4
Q

Basic router architecture/function

A
  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
5
Q

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

A
  • 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
6
Q

Design of the interconnect

A
  • 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
7
Q

Crossbar switch

A
  • 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
8
Q

Advantage of crossbar switching

A

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

9
Q

Maximal matching

A

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

10
Q

Speedup

A

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

11
Q

It’s common practice to run the interconnect at…

A

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.

12
Q

Virtual output queues

A

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

13
Q

2 important goals of scheduling

A

(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.
14
Q

Max-Min Fairness

A

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

15
Q

Formal procedure of max-min fairness

A
  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
16
Q

Why is it called max-min fairness

A

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

17
Q

How to achieve max-min fairness (3 approaches)

A
  • Round-robin scheduling
  • Bit-by-bit scheduling
  • Fair queueing
18
Q

Round-robin scheduling

A

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

19
Q

Bit-by-bit scheduling

A

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?

20
Q

Fair queueing

A
  • 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.