Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

CS313 > Chapter 3 > Flashcards

Chapter 3 Flashcards

1
Q

Datagrams

A

Include enough info in packets to indicate to a switch what the destination of the packet is.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Fowarding table

A

A switch consults a forwarding table to decide where to forward packets

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Datagram Characteristics

A
  • Connectionless
  • Host can send a packet anywhere at any time
  • This host doesn’t know whether or not that host is actually present on the network or if the network can actually deliver this packet.
  • Each packet is forwarded independently of one another.
  • Can usually use alternate routes to forward packets.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Virtual Circuit Switching

A

Set up a virtual connection between source and destination hosts.
Considered a connection-ortiented model

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Virtual Circuit Table

A

Setting up a connection state consists of an entry in a VC (Virtual Circuit) table in each switch through which the data will be transferred.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Virtual Circuit Identifier

A

Have unique identifiers for connections, called VCI (Virtual Circuit Identifier). Obviously, where a connection is not present in a table, a new, unique VCI is created and added to the table.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Permanent Connection State

A
  • Network Admin configures the state.
  • NA needs to determine a path and pick unsued VCI values
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Signalling Connection State

A
  • Host can send a message into the network to establish a state
  • Packet is routed from host A to host B as in datagrams, but each switch
    along the way creates entries to the VC table for the connection.
  • After all entries are created along the route, acknowledgements are sent back.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Teardown message for signalling

A

Host destroys connection to host B by sending a teardown message to it’s switch.
* Switch removes entry from table and forwards message

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Signalling Characteristsics

A
  • At least one RTT before data can be sent
  • If a switch or link is broken then a new connection has to be made
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Pros of Signalling

A
  • Once the ACK is received then we know a lot about the network
  • Can allocate resources to the VC to allow for a good QoS
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Comparison of VCI with Datagram

A
  • Datagram has no connection phase
  • Each arriving packet competes for available buffer space
  • If there are buffers the packet will be dropped
  • For each circuit in VC, each has its own QoS
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

User Network Interface

A
  • Generic Flow Control: GFC - 4
  • Virtual Pathway Identifier: VPI - 8
  • Virtual Cirtuit Identifier: VCI - 16
  • Management/CongestionControl: Type - 3
  • Cell Loss Priority: CLP - 1
  • CRC - 8
  • Payload 384
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Asyynchronous Transfer Mode

A
  • Connection oriented packet switched network
  • Packets = cells
  • Fixed packet size = Easier to switch
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Source Routing

A
  • All info about the topology is given by the source host to switch the packet
  • 3 methods used to get this information
  • Rotation
  • Stripping
  • Pointer
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Bridge

A
  • A node that forwards all LAN frames from one Ethernet to another Ethernet
  • Solves the repeater problem
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Limitations of using a repeater to connect Ethernet

A
  • No more than 4 repeaters in between hosts
  • No more than a total of 2500m
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Learning Bridges

A
  • Uses forwarding table so that it doens’t always just forward to ports
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Implementation of Learning Bridge

A
  • Build their own table
  • Look at each source address of each frame
  • Record the info
  • Timeout associated with each entry
  • If an address is not on the table, the frame gets forwarded to everyone
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Spanning Tree Algorithm

A
  1. Elect the bridge with the smallest ID as the root of the spanning tree
  2. Make root bridge forward frames out over all its ports
  3. Each bridge computes the shortest path to the root and notes which of its ports are on
    this route
  4. This port is selected as the bridge’s preferred path to the root
  5. All the bridges connected to a given LAN elect a single designated bridge that will be
    responsible for forwarding frames toward the root bridge. Chosen as closest to root.
  6. The bridge forwards frames over those ports for which it is the designated bridge.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Broadcast

A

each bridge forwards a frame with a destination broadcast address out on each active (selected) port other than the one on which the frame was received.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Multicast

A

same way, but each host decides whether or not to accept the frame. Can optionally prune the spanning tree for multicast messages

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Limitations of bridges

A
  • Not scalable
  • Spanning tree algo does not scale
  • Broadcast doest not scale
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Virtual LAN

A
  • Allow a single extended LAN to be partitioned into several seemingly separate LANs
  • Messages can only be sent between VLANs with same identifier
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Internetwork

A

collection of networks interconnected

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Networkq

A

a directly connected or switched network.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

Internet Protocol

A

Defines infrastructure that allows nodes and networks to a function as a single logical internetwork

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

Routers

A

Nodes which interconnect the networks

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

Packet Delivery Model

A
  • Connectionless model for data delivery
  • Best-effort delivery (unreliable service)
  • Packets are lost
  • Packets are delivered out of order
  • Duplicate copies of a packet are delivered
  • Packets are delayed for a long time
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

Global Addressing Scheme

A

Provides a way to identify all hosts in the network

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

Packet format for IP Service Model

A
  • Version - 4
  • Hlen: Number of bits in the header - 4
  • TOS : Type of service - 8
  • Length : Number of bytes in this datagram - 16
  • Ident : Used by fragmentation - 16
  • Flags : Used by fragmentation - 16
  • TTL : Number of hops this datagram has traveled - 8
  • Protocol : Demux key - 8
  • Checksum - 16
  • DestAddr & Src Addr - 32
32
Q

Fragmentation and Reassembly

A

Each network has some Maximum Transmission Unit
* Ethernet 1500 Bytes
* FDDI 4500 Bytes

33
Q

Fragmentation and Reassembly Strategy

A
  • Fragments have an Ident field (unique identifier).
  • Offset for each fragment to indicate where it is in terms of the entire packet. Where not all fragments arrive, all the fragments are dropped by destination.
  • Fragmentation happens on 8-byte boundaries.
  • Reassembly only done at destination address.
  • Fragmentation avoided (try to make packets as small as smallest MTU along path) because reassembly is not ideal.
34
Q

Global Addresses

A
  • Consist of a network and host part
  • Globally unique
  • 4 billion IP Addresses
35
Q

A type Global Address

A
  • 0
  • Network - 7
  • Host - 24
  • 10.3.2.4
36
Q

B type Global address

A
  • 1
  • 0
  • Network - 14
  • Host
  • 128.96.33.81
37
Q

C type Global Address

A
  • 1
  • 1
  • 0
  • Network - 21
  • Host - 8
38
Q

Datagram Forwarding in IP

A
  • Forwarding: process of taking a packet from an input and sending it to the appropriate output
  • Routing: Process of building up tables that allow correct output for a packet to be determined.
  • Any node, whether it is a host or a router, first tries to establish whether it is connected to the same physical network as the destination by checking network part of address.
  • Otherwise, datagram sent through routers. Uses routers with best nextHop.
39
Q

Network Fowarding Algorithm

A

if (NetworkNum of destination = NetworkNum of one of my interfaces) then
* deliver packet to destination over that interface

else
* if (NetworkNum of destination is in my forwarding table) then
* >deliver packet to NextHop router
else
* deliver packet to default router

40
Q

Subnetting

A
  • taking a single IP network number and allocating IP addresses with that network number to several networks
41
Q

Subnet Mask

A

Used with an IP address (bitwise AND) to determine the subnet number of the host

42
Q

Subnetting forwarding algorithm

A
  • When a host wants to send a packet, we take the bitwise AND of the source’s subnet mask and the destination IP address to determine if source and destination are in the same subnet.
  • Otherwise, sent to a router and forwarded.

Forwarding table now needs to include the following properties:
● Subnet number
● Subnet mask
● Next hop
To find the right entry in this forwarding table, we bitwise AND the destination IP with each row’s subnet mask and see if this result matches the subnet number.
Default route used if no matches are found.

43
Q

Classless Interdomain Routing

A

Do away with address classes altogether. Keeps routing system from being overloaded and tackles address problem.

44
Q

Why - ClDR

A

Consider the following example.
1. An organisation has 256 hosts.
* Assign a B class address -> efficiency = 256/65536 BAD
* Assign an address to each host. Leads to excessive routing tables. In this case,
256 entries in a routing table.
2. An organisation has 16 hosts.
* Assign an address to each host -> efficiency = 16 * 255/65536 BAD. Again, excessive routing tables.
Let’s balance number of entries in a routing table versus handing out of addresses.

45
Q

CIDR Problems

A
  • Excessive Storage req. at the routers for all the type C addresses
  • If a single AS has 16 class C network numbers assigned to it, each router will now need 16 entries in its routing table for that AS
  • Any type B addresses can be stored in C but with 6.2% efficiency
46
Q

CIDR Aggregate Routes

A
  • Uses a single entry in the forwarding table to tell the router how to reach a lot of different networks
  • Breaks the rigid boundaries between address classes
  • Instead of sending out 16 entries where the suffix is the same just send a block of contiguous class C addresses
  • Uses /X to send a block of X length
47
Q

IP Forwarding with CIDR

A
  • All routers must understand CIDR
  • Represent network number with single pair < length, value >
  • Routers must understand that network numbers may be of any length
  • Works on the longest match if you have variable sized batches, the most correct one works
48
Q

Address Translation Protocol(ARP)

A

Need to translate IP address to a link-level address which makes sense on the network. Can encapsulate the IP datagram in a frame with the link-layer address and send this on it’s merry way to reach the address.

49
Q

ARP Techniques

A
  1. Can encode host’s physical address in the host part of it’s IP address
  2. table-based
    * table of IP to physical address bindings
    * boradcast request if IP address not in table
    * target machine responds with its physical address
    * table entries are discarded if not refreshed
50
Q

ARP Packet Format

A
  • Hardware type
  • Protocol type
  • HLEN & PLEN : length of physical and protocol address
  • Operation: request or response
  • Source/Target Physical/Protocol Address
51
Q

Host Configuration

A
  • IP addresses must be unique and reflect structure of internetwork.
  • IP addresses need to be reconfigurable.
  • In addition to an IP address, hosts need to know address of default router when sending packets.
52
Q

Dynamic Host Configuration Protocol (DHCP)

A

Automated configuration method to assign IP addresses to hosts on a network

53
Q

DHCP Server

A
  • Provides the configuration info to hosts
  • There is at least one DHCP Server for an an admin domain
  • DHCP server maintains a pool of available addresses and hands out on demand
54
Q

How to contact DHCP Server

A
  • Hosts sends DHCPDISCOVER message to 255.255.255.255
  • Received by all hosts on the the network
  • The server then replies to the host
  • DHCP relay agent is actually on the network and then sends the message to the served and awaits response
55
Q

Internet Control Message Protocol (ICMP)

A

Defines a collection of error messages that are sent back to the source host whenever a router or host is unable to process an IP Datagram successfully
* Dest/ host unreachable due to link/node failure
* Reassembly process failed
* TTL had reached 0 ( so datagrams don’t cycle forever )
* IP header checksum failed

56
Q

ICMP Redirect

A
  • From router to source host
  • With a better route info
57
Q

Forwarding vs Routing

A

Forwarding:
* to select an output port based on destination address and routing table

Routing
* process by which routing table is built

58
Q

Forwarding table vs Routing table

A

Forwarding table
* Used when a packet is being forwarded and so must contain enough information to accomplish the forwarding function
* A row in the forwarding table contains the mapping from a network number to an outgoing interface and some MAC information, such as Ethernet Address of the next hop

Routing table
* Built by the routing algorithm as a precursor to build the
forwarding table
* Generally contains mapping from network numbers to next hops

59
Q

Virtual Private Networks (VPN)

A
  • to control connectivity
  • Communication restriced to take place among sites of an organisation
60
Q

IP Tunnel

A

acts as a virtual point-to-point link between a pair of nodes that are separated by networks.

61
Q

Sending IP Datagrams

A
  • When sending IP datagrams across the networks, destination address set to that of the router at the far end of the tunnel.
  • Whereas source address set to the encapsulating router.
  • Payload then has actual destination address.
  • When an IP datagram is sent from one end of the tunnel to another end of the tunnel, it may have to go through an internetwork to reach the other end.
  • What the router at the entrance to the internetwork does is add an IP header to the original IP datagram.
  • This newly added IP header then essentially specifies to the internetwork is how to reach the other router at the receiver end of the tunnel.
  • Once the router at the receiver end of the tunnel gets this datagram, it strips the added IP header and forwards the datagram onto the correct host.
  • This way the receiving host will know by inspecting the original IP header that the datagram was sent through the tunnel.
62
Q

Routing Table Format vs Forwarding Table Format

A

Routing:
* Prefix/Length
* Next Hop

Forwarding
* Prefix/Length
* Interface
* MAC Address

63
Q

Distance Vector

A
  • Each node constructs a 1D array containing all distances to all other nodes and distributes this vector to all its neighbours.
  • Initial assumption is only nodes adjacent are on the table
64
Q

When a node detects failure - Distance Vectore

A
  • F detects that link to G has failed
  • F sets distance to G to infinity and sends update to A (Neighbour)
  • A sets distance to G to infinity since it uses F to reach G
  • A receives periodic update from C with 2-hop path to G
  • A sets distance to G to 3 and sends update to F
  • F decides it can reach G in 4 hops via A
65
Q

Testing link failure

A
  • Send control packets to neighbours and see if the acks received
  • No periodic routing updates received for a few cycles
66
Q

Counting to Infinity Problem

A
  • Suppose the link from A to E goes down
  • In the next round of updates, A advertises a distance of infinity to E, but B and C advertise a distance of 2 to E
  • This causes an infinite cycles of updates causing the length to increase because there technically should not be a path available but there is
67
Q

Solution 1 for Counting to Infinity Problem

A

Use a relatively small number to approx. infinity.

68
Q

Solution 2 for CtIP - Split Horizon

A

when a node sends a routing update to its neighbors, it does not send those routes it learned from each neighbor back to that neighbor.

69
Q

Split Horizon with Poison Reverse

A

Send back to neighbour but with infinite distance

70
Q

Routing Information Protocol (RIP)

A

Rather than advertising the cost of reaching other routers, the routers advertise the cost of reaching networks. Uses the distance vector stuff as well for determining costs.

71
Q

Link State Routing

A

Each node is assumed to be capable of finding out the state of the link to its neighbors (up or down) and the cost of each link.

72
Q

Link State Packet

A
  • id of the node that created the LSP
  • Cost of the link to each directly connected neighbour
  • Seqeunce number
  • Time to Live for this packet
73
Q

Reliable Flooding

A
  • store the most recent LSP from each node
  • Forward LSP to all nodes but one that sent it
  • Generate new LSP periodically
  • Incremenr Sequence Number
  • Start sequence number at 0 when reboot
  • decrement TTL of each stored LSP
  • Discard when TTL = 0
74
Q

Shortest Path Routing

A
  • Dijkstra’s Algorithm - Assume non-negative link weights
  • N: set of nodes in the graph
  • I(i, j): the non negative cost associated with the edge between the nodes
  • let s be the starting node
  • M: the set of nodes incorporated so far by the algorithm
  • C(n): the cost of the path from s to each node n
75
Q

Dijkstra’s Algo

A
  • Initialize the Confirmed list with an entry for myself; this entry has a cost of 0
  • For the node just added to the Confirmed list in the previous step, call it node Next, select its LSP
  • For each neighbor (Neighbor) of Next, calculate the cost (Cost) to reach
    this Neighbor as the sum of the cost from myself to Next and from Next
    to Neighbor
    • If Neighbor is currently on neither the Confirmed nor the Tentative list, then add (Neighbor, Cost, Nexthop) to the Tentative list, where Nexthop is the direction I go to reach Next
    • If Neighbor is currently on the Tentative list, and the Cost is less than the currently listed cost for the Neighbor, then replace the current entry with (Neighbor, Cost, Nexthop) where Nexthop is the direction I go to reach Next
  • If the Tentative list is empty, stop. Otherwise, pick the entry from the Tentative list with the lowest cost, move it to the Confirmed list, and return to Step 2.
76
Q

Open Shortest Path First Protocol (OSPF)

A
  • Need to authenticate routing messages
  • 8-byte password authentication
  • Multiple routes allowed with the same costs - distribution of traffic
77
Q

Pros and Cons of Link-State algorithm

A

Pros
* Stabilises quickly
* Doesn’t generate much traffic
* Responds rapidly to topology changes

Cons
* A lot of info stored at each node

CS313 (9 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions