Midterm 1 Flashcards Preview

CS 6250 > Midterm 1 > Flashcards

Flashcards in Midterm 1 Deck (52):

What is ARP and how is it used?

Address Resolution Protocol - Broadcast query to discover an IP to MAC mapping with a unicast response of the MAC from the target IP.


What is a NAT?

Network Address Translation - Converts to/from public IP:Port to private IP:Port on the local network. Replaces the source IP upon leaving the NAT to the public and replaces the destination IP upon entering the NAT to the local network.


What is the STP? Explain it's purpose.

Spanning Tree Protocol - Physically can have redundant links (topology loops), but ports switched off at the logical layer so that there are no loops. Ports can then be switched back on if necessary in case something else goes down.


What is the narrow waist?

Internet Protocol (IP) (AKA Network Layer) is the center of the waist. Every internet device must implement the IP stack. Provides guarantees to above layers: End-to-end connectivity with best effort delivery. This is about the only requirement to 'get on the internet'.


What is the end to end principle?

As much functionality as possible should be implemented at the endpoints, not in the middle. Keeps core IP very simple. Allows innovation at the endpoints. It's not doing more than you need. "Dumb Network, Intelligent Endpoints"


What is the longest matching prefix length?

The most specific subnet, eg: /20 is more descriptive than /16. You should forward according to the longest prefix.


What is an autonomous system?

An independently operated network.


List advantages/disadvantages of packet switching.

Advantages: No busy signal! The links are shared so multiple people can use the same paths. Potentially better resilience properties.

Disadvantages: Variable delay, potential for lost or dropped packets.


List advantages/disadvantages of circuit switching.

Advantages: resource control, better accounting, reservation of resources, ability to pin paths b/t sender/receiver. Better throughput as the only congestion is your own.

Disadvantages: Only one person can use a given path at any one time. More difficult to design and implement.


What is a broadcast storm?

Loop connections where one broadcast is sent to a switch which emits the same broadcast which goes back to the source which re-emits it and it continues in a loop this way.


What is fate sharing?

Acceptable to lose state information for that entity if the entity is lost itself. State in device shares the fate of the device itself.


What were the original goals of the internet?

Main Goal: "Multiplexed utilization of existing interconnected networks"

Smaller Goals:
Interconnection - Support multiple types of communication services (protocols)
Work on a variety of networks - physical layers
Survivability - Network works even if some devices fail
Distributed Management - No single owner
Cost Effectiveness - 'fairly' cost effective as it is
Ease of Attachment - Narrow Waist makes it easy to use optical, cable, or wireless (physical layer). Anything that wants to be on the internet just needs to speak IP - that's it.
Accountability - ability to bill. Harder in the current internet of packet switching than if it was circuit switched.


What are the major layers of the OSI network model?

Application Layer: HTTP/SMTP/etc.
Transport Layer: provides 'reliably transport', 'congestion control' (TCP/UDP)
Network Layer: "IP over anything"
Link Layer: often Ethernet (p2p connectivity)
Physical Layer: optical, electrical, etc


What are some violations of the end-to-end argument?

NAT, VPN Tunnels, TCP splitting, Spam (network _should_ deliver _all_ main to user, but with spam, sometimes it gets filtered), P2P, Caches


How does NAT violate the end-to-end argument?

It interferes by rewriting the source and destination ports as they go in and out of the router's NAT. Machines behind the NAT aren't publicly addressable.


What is the difference between switches, hubs, and routers?

Hubs: broadcast medium - all packets are seen everywhere.
Switch: Isolates Traffic - only forwards packets to the ports where the destination is. Typically operate at layer 2. Major limitation: broadcast - spanning tree/arp queries can eat up a lot of bandwidth.
Routers: Typically operate at layer 3 (IP layer). Topologies are not restricted to a spanning tree. Can have multiple paths to the same destination.


What is a switch table (forwarding table)?

A mapping of host IP's to output ports.

1. If entry is not found in table, it floods (broadcasts)
2. It will forward ARP requests properly (broadcasts)
3. If entry exists, it will just send to that port


How does STP work?

1. Elect a root (swtich w/ smallest ID) - initially every node assumes it is the root.
2. At each switch, exclude link if not on the shortest path to root
3. Tiebreakers go to the node with the smallest ID

- Messages are passed with the (origin, claimed root, and distance to claimed root)
- Each switch adds 1 to the distance received in the message and checks to see if msg claimed root is < it's claimed root, if so it updates claimed root and its distance to claimed root.


How are buffering needs determined in router/switch design?

used to be 2T*C, but now it's 2T*C/sqrt(n).

2T*C only applies if flows are synchronized. If they are not synchronized, they gaussian becomes narrower as a function of 1/sqrt(n).


Define the major two types of routing.

Interdomain: Routing outside an AS
Intradomain: Routing inside an AS


What is a POP?

Point of Presence - node in an AS located near population centers.


What kind of routing are supported for domains?

- Distance Vector Routing (Bellman Ford Equation)
- Link State Routing


What is the count to infinity problem?

When nodes are either counting in a loop towards negative infinity or counting up toward some value they must exceed due to bellman ford (min[cur_val, new_val + dist])


What is a poison reverse?

Setting a node value to infinity and rebroadcasting out so that you avoid a count to infinity problem. This forces another node not to go through you to get to another destination.


What is link state routing?

Alternative to RIP, used in most networks today.

Each node distributes it's network map to it's neighbors and performs shortest path (SPF) computation (Dijkstra).

Link state routing is O(n^3)


What is RIP?

- Routing Information Protocol
- Edges have a unit cost
- infinity = 16
- slow convergence
- can take minutes to stabilize if a router fails


What is BGP?

Border Gateway Protocol

- Destination: Final destination IP address
- Next Hop: ip of the next hop in path
- AS-Path: sequence of AS numbers route took to get where it is. Last number is origin.


What is eBGP?

External BGP - transmitting routing info b/t border routers of adjacent AS's about external destinations.


What is iBGP?

Internal BGP - disseminating BGP route adverts about external destinations to routers inside any particular AS.


What is IGP?

Intradomain Gateway Protocol

Routes inside an AS to INTERNAL destinations.


Explain the BGP Route Selection Process

1. Prefer Higher "local preference" (dropped in eBGP adverts)
2. Shortest AS path length
3. Mult-Exit Discriminator (MED) - Allows an AS to advertise it would prefer you to use a specific exit point from their AS. Lower values are more preferable. Only matters when comparing routes through the SAME AS.
4. Shortest IGP Path -> results in hot-potato routing. Traverses as little of its own internal network as possible.
5. Tiebreak -> arbitrary, but often lowest router ID


Describe Local Preference in BGP routing

If multiple paths exist to the same destination, admin can set a higher local pref value for that route so it gets used by a given router.

Allows them to control OUTBOUND traffic from their AS.

Useful for configuring a primary/backup route.


What is a BGP 'Community'?

A 'tag' on a route. Could advertise a route with a community value of 'backup' or 'primary'. This could let a neighboring AS's know which route to select based on this value. Requires prior agreement between parties.


What is the Multiple Exit Discriminator (MED)?

Value that tells who you're broadcasting to which route you would prefer them to use when they send data through you. Lower values are higher priority. If no MED value was used, could have hot-potato routing from neighboring AS so it uses whichever link is shortest to exit. If advertising with MED values, you could control which link was used because MED evaluation comes before IGP shortest path evaluation. MED override hot-potato routing behavior.


When learning BGP routes, who would you re-broadcast the route to depending on who the route is from?

From Customer: To Everyone
From Provider: Only to Customers
From Peer: Only to Customers


What rank (export rules) is it best to send data to once routes are established?

Customer > Peer > Provider


What is CIDR?

Classless Interdomain Routing - No longer using Class A, B, or C network classes. Just use subnets with net masks.


Describe prefix aggregation with respect to ip forwarding.

If multiple endpoints (say and are only reachable through one host with a shorter prefix (eg,, then you only need to advertise the shorter prefix. Once it gets to the shorter prefix, they will take care of sending it to the proper location.


What is multihoming?

it 'frustrates' aggregation - basically makes it not possible. If Verizon and ATT both connect to an AS, and ATT advertises, and the AS is a subnet of ATT @, then ATT can't aggregate the IP because the AS would still be advertising the longer prefix to Verizon. Since longest prefix match wins, all data going to the AS would come through Verizon. As a result, both ATT/Verizon must advertise the /24 address.


How could you control inbound traffic via longest prefix match?

By advertising two prefixes - one which is a little longer to split the area, eg: and and 12.12.128/17

This is deaggregation. Since longest prefix match wins, you can control the inbound traffic by splitting it up by the more specific IP. If one of those fails, you still have the shorter IP to ensure traffic gets to you.


What is a trie (wrg to addres lookups)?

A data structure. A sort of binary tree where a 1 takes you to the right and a 0 takes you to the left (in the case of a single bit trie). A single bit trie could take as many as 32 accesses to find a 32 bit address.


How is a multi-bit (multi-ary) trie built?

W = total # of bits to resolve
K = Number of bits per level
Depth = W / K
Degree = 2^K
Stride = K


What alternative is there to LPM w/ tries?

CAM - Content Addressable Memory - But this is O(1) since you're looking up every address
Ternary CAM (0, 1, *) - Permits an implementation of LPM because you can implement a * or don't care.


What does the basic routing architecture look like?

1. Receive Packet
2. Get destination from header
3. Look at forwarding table to determine output interface
4. Modify Header (eg, TTL)
5. Send packet to output interface


What is crossbar switching?

AKA, Switch Backplane - Every input port has a connection to an output port. During each timeslot, every input is connected to zero or 1 outputs.


What is the Maximal Matching algorithm?

In each timeslot, you want a 1:1 mapping between inputs and outputs. Hence a goal of maximal matching.


What is a virtual output queue?

A queue for each output port at each input. This gives the input port access to any packets destined for any output port. This means packets destined for one output port won't block the queue because the input port has access to all the queues.


What is max-min fairness?

Small demands get what they want, larger demands get what is left after filling the smaller demands.

EG: 10Mbps with demands [1, 3, 5, 6]

10 / 4 =2.5
Result: [1, 3, 3, 3]


How can you achieve Max-Min fairness?

Round Robin: No good b/c of varying packet sized (not actually fair)
Bit by Bit: Fair but not feasible.
Fair Queueing: Service packets according to the soonest 'finishing time'


What type of DNS records are there?

A record: Name -> IP Address (Authoritative)
NS record: Name -> another authoritative nameserver
MX record: Name -> mail server
CNAME - canonical name
PTR record: IP -> Name (reverse lookup)
AAAA record: name -> ipv6 address


What is OSPF?

A Link state routing - Open Shortest Path First


What is IS-IS?

A link state routing - Intermediate-System to Intermediate-System