5.1-Router Design Basics Flashcards
Need for big, fast routers
Links are getting faster
Demands are increasing (i.e streaming video)
Networks are getting bigger too
1) Recieves a packet
2) Look at header to determnine destination
3) Look in forwarding table to determine output interface
4) modifies header (i.e.ttl)
5) send packet to output interface
Basic router function
Basic I/O component of a router architecture
An interface in which a router sends and receives data
Line card (I/O)
Decision 1: Prevents a central table from becoming a bottleneck at high speeds
Putting a copy of the forwarding table on each line card of the router. eliminating the shared bus.
Decision 2: How should the line cards be connected to one another?
Crossbar Switching
- Every input port has a connection to every output port
* During each timeslot, each input is connected to zero or one outputs
Crossbar Switching
advantage is parallelism
Switching Algorithm: Maximal Matching
N inputs, N outputs
Speed up may not help
Head of Line Blocking
Solution: Virtual Output Queues
Man - Min Fairness
Flow allocation :{x1, x2, ….., xn}
Increasing any rate xi -> some other xj < xi must be decreased
small demands get what they want
large users split the rest of the capacity
1st Example: Max-Min Fairness
Demands: [2, 2.6, 4, 5] Capacity: 10
The demand exceeds capacity.
10/4 = 2.5 first user only needs 2 so there is an excess of 0.5.
Divide 0.5 by 3 (remaining 3 users) = 0.167
=[2,2.67,2.67,2.67] 2nd user only needs 2.6 so there is an excess on 0.07
Divide 0.07 by remaining 2 = 0.035
=[2,2.6,2.7,2.7] = Final max-min fair allocation
This maximizes the minimum share to each user whose demand is not fully services. In this case, the 3rd and 4th users.
2nd Example: Max-Min Fairness
Demands [1,2,5,10] Capacity: 20
Demand does NOT exceed the capacity
20/4 users = 5
[5, 5, 5, 5]
[1 because this is the 1st user’s max so we have 4 excess
, 2 because this is the 2nd user’s max so we have 3 excess
5 is the max we can give so already there.
Add the excess to the last one which is 5 + 7 = 12
=[1,2,5,12] Final max-min fair allocation
How to achieve Max-Min fairness?
1) Round-Robin scheduling (problem” packets may have different sizes)
2) Bit by Bit scheduling (this is better but problem is feasibility)
3) “Fair Queuing” -> service packets according to their soonest finishing time (Queue whose packet has the minimum virtual finishing time is serviced)
